It's Christmas time, which means it's time for a very sunny secret santa!!! This year, Max (Sun) begs Aaron to buy him a guitar; he's always wanted to play, but never had the time to learn. On Christmas Day, Max rushes downstairs to open the massive gift-box that Aaron sent him.

Max doesn't want to disrespect Aaron's gift, so he tries to learn as many chords as he can on the guitar. His new guitar contains ~N~ different strings, the ~i^{th}~ of which has a wavelength of ~a_i~. Max doesn't know how to use the guitar fretboard, so he decides to only play open strings. In other words, Max will only be able to make one note for each string on his guitar.

Max defines a chord as a consecutive subset of strings. The quality of a chord is defined as ~W_F \times F~, where ~W_F~ is the most frequent wavelength and ~F~ is the number of times it is played in a chord. If two wavelengths are equally frequent, ~W_F~ is equal to the higher value.

Additionally, Max has ~M~ fingers. Each of these fingers can play up to one distinct string. Given these constraints, Max wonders how many unique chord qualities he can learn to impress Aaron. As Max's best friend, please help him out!

Input Specification

The first line will contain two integers, ~N~ and ~M~ (~1 \le M \le N \le 5 \times 10^3~), the number of strings on Max's new guitar and the number of fingers Max has.

The second line will contain ~N~ space-separated integers ~a_1, a_2,..., a_N~ (~1 \le a_i \le 5 \times 10^3~), which denotes the wavelength of the ~i^{th}~ string when played open.

Output Specification

Output one integer, the number of unique chord qualities he can play given the constraints.

Subtasks

Subtask 1 [10%]

All ~a_i~ are distinct.

Subtask 2 [20%]

~1 \le M \le N \le 500~

Subtask 3 [70%]

No additional constraints.

Sample Input 1

7 2
1 1 2 3 3 2 1

Sample Output 1

4

Sample Explanation 1

With one finger, Max can create the following chords with qualities of:

• ~1~ with ~[1, 1]~, ~[2, 2]~ and ~[7, 7]~
• ~2~ with ~[3, 3]~ and ~[6, 6]~
• ~3~ with ~[4, 4]~ and ~[5, 5]~

With two fingers, Max can create chords with qualities of:

• ~2~ with ~[1, 2]~, ~[2, 3]~ and ~[6, 7]~
• ~3~ with ~[3, 4]~ and ~[5, 6]~
• ~6~ with ~[4, 5]~

Thus, the set of distinct qualities Max can create is ~\{1, 2, 3, 6\}~.

Sample Input 2

20 10
1 3 5 7 1 3 5 7 1 3 5 7 12 2 12 2 1 2 3 1

Sample Output 2

14