There are a lot of Poke'mons who are jealous of the fact that they do NOT have any specialty, they're the... normal type of Poke'mon. But, what they fail to realize is that their power is their normalcy, the ability to think, rationalize and then act.
But, they do have an additional power... Poke'mons like Jigglypuff - which are normal, can figure out if a trainer is real or is a part of Team Rocket. And they need to use their power to a great extent.
In an array, which consists of N elements, A1, A2, ..., AN, if a subarray has the total number of distinct elements as that of the original array, that determines the presence of Team Rocket.
You've to help the normal type Poke'mons in figuring out the total number of subarrays having total number of distinct elements same as that of the original array.
Input format:
The first line of the input will consist of a single integer N. The next line will consist of N integers A1, A2, ... , AN.
Output format: Output the answer to the problem.
Constraints:
1 = N = 2 * 10^5
1 = Ai = 10^9
Sample:
INPUT:
5
1 2 2 1 1
Output:
8
Explanation:
All the possible subarrays are [1,2] , [1,3] , [1,4] , [1,5] , [2,4] , [2,5] , [3,4] , [3,5]
We need to find the number of subarrays [i..j] so that the number of distinct elements in i..j is equal to the number of distinct elements in the entire array. Here is a step by step approach to solve the problem. In case you are looking for hints for the solution and not the entire solution itself, please read till step 2.
Step 1: Find the number of distinct elements in the entire array, let this number be denoted as num_dist
Step 2: For each index, denote next[index] as the smallest j such that j > index and array[index] = array[j].
Step 3: Sweep through the integers from N to 1, keep a set of which contains the last position of all of the distinct integers (so, the number of elements in this set should be <= num_dist. If the number of elements in the set is < num_dist, then we know that we haven't seen all the distinct integers yet).
Step 4: Let maxi denote the maximum integer in this set at the current index. If the number of integers in the set is not equal to num_dist, then we haven't seen all the distinct numbers yet, so we do nothing. Otherwise, we add N - maxi + 1 to the answer, because [index..maxi], [index..maxi+1], .. [index..N] all contain all of the distinct numbers.
Essentially, we are just sweeping from N to 1 and fixing the current index as the left endpoint of the subarray and counting number of valid right endpoints for that left endpoint
