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?

$$$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.