F. The Number of Subpermutationstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou have an array a_1, a_2, \dots, a_n. Let's call some subarray a_l, a_{l + 1}, \dots , a_r of this array a subpermutation if it contains all integers from 1 to r-l+1 exactly once. For example, array a = [2, 2, 1, 3, 2, 3, 1] contains 6 subarrays which are subpermutations: [a_2 \dots a_3], [a_2 \dots a_4], [a_3 \dots a_3], [a_3 \dots a_5], [a_5 \dots a_7], [a_7 \dots a_7].You are asked to calculate the number of subpermutations.InputThe first line contains one integer n (1 \le n \le 3 \cdot 10^5).The second line contains n integers a_1, a_2, \dots , a_n (1 \le a_i \le n). This array can contain the same integers.OutputPrint the number of subpermutations of the array a.ExamplesInput
8
2 4 1 3 4 2 1 2
Output
7
Input
5
1 1 2 1 2
Output
6
NoteThere are 7 subpermutations in the first test case. Their segments of indices are [1, 4], [3, 3], [3, 6], [4, 7], [6, 7], [7, 7] and [7, 8].In the second test case 6 subpermutations exist: [1, 1], [2, 2], [2, 3], [3, 4], [4, 4] and [4, 5].
8
2 4 1 3 4 2 1 2

7 
['brute force', 'data structures', 'divide and conquer', 'hashing', 'math', '*2500']