Incomplete Color#13095
You are given an array of length . Each number represents a color.
Consider a subarray a_l,a_{l+1},\ldots,a_r. A color is called incomplete in this subarray if the subarray contains at least one occurrence of this color, but not all of its occurrences in the original array.
For example, if a color occurs five times in the original array, it is incomplete in any subarray containing between one and four of its occurrences.
A subarray is called good if it contains exactly one incomplete color. Every other color must either be absent from the subarray or have all of its occurrences in the original array included in the subarray.
Find the number of good subarrays.
The first line contains an integer (1 \leq n \leq 2 \cdot 10^5) — the length of the array.
The second line contains integers a_1,a_2,\ldots,a_n (1 \leq a_i \leq n) — the colors of the array elements.
Print one integer — the number of good subarrays.
Example 1
Example 2
Example 3
In the first example, there are good subarrays. For instance, in the subarray a_1,a_2,a_3, color is incomplete, while all occurrences of color are included. The subarray a_1,a_2 is not good because it contains two incomplete colors.
In the second example, every nonempty subarray except the whole array contains incomplete color . There are such subarrays.
In the third example, each color occurs exactly once in the original array, so no color can be incomplete. There are no good subarrays.
points — all array elements are equal.
points — n \leq 100.
points — n \leq 2000.
points — a_i \leq 2.
points — the array contains at most distinct colors.
points — no additional constraints.