Warith has been coping for a while about not being able to see Le Sserafim in Dallas, so he decided to take a mental break. He decided to go down to the Colorado River and skip some stones. When he arrived, he found $$$n$$$ stones arranged in a line. Warith knows that each stone has some mass $$$a_i$$$ $$$(1 \le i \le n)$$$. With all the stuff on his mind, he wants to maximize his enjoyment from skipping stones by picking a contiguous subarray $$$a'$$$ of the original stone array. Note that Warith cannot rearrange the stones, he can only pick a contiguous subarray from the original order.
For an array $$$a'$$$, the enjoyment from skipping all these stones is calculated as follows:
The only issue is that Warith also does not want the mass of the stones to vary too much either. Specifically, he doesn't want his subarray to contain more than $$$k$$$ distinct masses. With this in mind, can you help Warith maximize his enjoyment?
The first line of input will contain two integers $$$n$$$ ($$$1 \le n \le 10^5$$$) and $$$k$$$ ($$$1 \le k \le n$$$): the number of stones, and the max number of permitted unique masses.
The second line contains $$$n$$$ integers ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the mass of the $$$i$$$th stone.
Output a single integer $$$E$$$: the maximum enjoyment Warith can achieve.
8 31 7 2 3 2 2 1 7
16
In the sample test case, the optimal range is $$$[7, 2, 3, 2, 2]$$$, which has enjoyment $$$(7)(1) + (3)(1) + (2)(3) = 16$$$.
