Subarray Tuple Frequency Conditions

Given a sequence of positive integers \(a_1, a_2, \cdots, a_n\) of length \(n\) and a constant \(k\), count the number of pairs \((l, r)\) such that:

• \(1 \le l \le r \le n\);
• For every integer \(i\) in \(1 \le i \le k\), there exists an integer \(x\) that appears exactly \(i\) times in the subarray \(a_l, a_{l+1}, \ldots, a_r\).

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(k\). The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer, the number of \((l, r)\) pairs satisfying the condition.

sample

3 2
1 2 1

1