Valid Weekly Schedule Selection

You are given a sequence of n courses, where each course is represented by a positive integer (not exceeding n). A student may choose a contiguous subsequence of the courses as a weekly learning schedule. However, the schedule must satisfy the following conditions:

• The chosen subsequence must include at least l courses. In addition, note that even if l is 1, a schedule with only one course is considered invalid because the first and the last course (which are the same in that case) must be different. Thus, effectively, the subsequence length must be at least max(l,2).
• No two consecutive courses in the chosen subsequence are the same.
• The first and the last courses of the chosen subsequence must be different.

Two selection schemes are considered different if their starting or ending positions in the original sequence differ. Your task is to count the number of valid weekly schedule selection schemes.

The conditions can be written in LaTeX as follows:

Let the course sequence be \(a_1, a_2, \dots, a_n\). A contiguous subsequence \(a_i, a_{i+1}, \dots, a_j\) is valid if:

[ \begin{aligned} & j-i+1 \geq L, \quad \text{where } L=\max(l,2),\ & a_k \neq a_{k+1} \quad \text{for all } i \leq k < j,\ & a_i \neq a_j. \end{aligned} ]

Count the number of valid selections.

inputFormat

The first line of input contains two integers n and l, where 1 ≤ n ≤ 10⁵ (assumed) and 1 ≤ l ≤ n.

The second line contains n positive integers representing the course types.

outputFormat

Output a single integer representing the number of valid weekly schedule selection schemes.

sample

5 2
1 2 1 2 3

8