407866: GYM102911 B2 Biodiverse Subarray

B2. Biodiverse Subarraytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The problem statements of Biodiverse Subsequence and Biodiverse Subarray are nearly identical, save for whether the sampled corals must form a subsequence or subarray of the given sequence. Despite this, the two are very different problems.

Biodiversity is one of the most important properties in any ecosystem, whether it's in a forest, a mangrove, or even the ocean. The Philippines is rich with species of flora and fauna that are endemic to the country. Cindy, an avid scuba diver, has accompanied a group of biologists that ventured to the Verde Island Passage to sample some coral species for their research. Of course, it is important that the samples that they choose properly reflect the diversity of marine life found at the Coral Triangle.

They find a row of $$$N$$$ corals and identify $$$K$$$ distinct species among them. We model this as a sequence of $$$N$$$ positive integers $$$A_1, A_2, \dots, A_N$$$. Each of the integers from $$$1$$$ to $$$K$$$ appears at least once, and these are the only integers to appear in the sequence. A sequence of numbers is called biodiverse if each of the integers from $$$1$$$ to $$$K$$$ appears at least once each in the sequence.

To preserve the properties of the habitat, the researchers must choose a biodiverse subarray of corals to sample from. A subarray is a contiguous subsequence of elements $$$A_l, A_{l+1}, \dots A_r$$$ where $$$1 \leq l \leq r \leq N$$$. In order to make a decision on which corals to sample, the researchers ask Cindy to count the number of biodiverse subarrays of $$$A$$$.

Help Cindy out?

Input

The first line of input contains two space-separated integers $$$N$$$ and $$$K$$$, the number of corals and the number of distinct species, respectively.

The second line of input contains $$$N$$$ space-separated integers $$$A_1$$$, $$$A_2$$$, $$$\cdots$$$, $$$A_N$$$, where $$$A_i$$$ is the species of the $$$i$$$th coral in the row.

Output

Output a single line containing a single integer, the number of biodiverse subarrays of $$$A$$$.

Scoring

$$$1 \leq K \leq N \leq 2\cdot 10^5$$$

$$$1 \leq A_i \leq K$$$ for all $$$i$$$.

There exists an $$$i$$$ such that $$$A_i = k$$$ for all $$$k$$$ from $$$1$$$ to $$$K$$$.

Subtask 1 (40 points):

$$$N \leq 100$$$

Subtask 2 (20 points):

$$$N \leq 2000$$$

Subtask 3 (20 points):

$$$K \leq 2$$$

Subtask 4 (20 points):

No further constraints.

ExamplesInput

4 2
1 2 1 2

Output

6

Input

14 9
3 1 4 1 5 9 2 6 5 3 5 8 9 7

Output

3

Note

The below diagram shows the six biodiverse subarrays that the researchers can choose from in the first sample test case.

The below diagram shows the three biodiverse subarrays that the researchers can choose from in the second sample test case.