F. The Number of Subpermutations
brute force; data structures; divide and conquer; hashing; math
You 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.
The 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.
Print the number of subpermutations of the array \(a\).
There 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]\).