1175_F. The Number of Subpermutations
You have an array a_1, a_2, ..., a_n. 

Let's call some subarray a_l, a_{l + 1}, ... , 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 ... a_3], [a_2 ... a_4], [a_3 ... a_3], [a_3 ... a_5], [a_5 ... a_7], [a_7 ... a_7].

You are asked to calculate the number of subpermutations.

Input

The first line contains one integer n (1 ≤ n ≤ 3 ⋅ 10^5).

The second line contains n integers a_1, a_2, ... , a_n (1 ≤ a_i ≤ n). 

This array can contain the same integers.

Output

Print the number of subpermutations of the array a.

Examples

Input


8
2 4 1 3 4 2 1 2


Output


7


Input


5
1 1 2 1 2


Output


6

Note

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].
```python
#import  sys
import  math
#input=sys.stdin.readline
#sys.setrecursionlimit(1000000)
mod=int(1000000007)
i=lambda :map(int,input().split())
n=int(input())
a=[int(x) for x in input().split()]
t=[[0]*21 for i in range(300005)]
for i in range(n):
    t[i][0]=a[i]

def build(n):
    for j in range(1,20):
        for i in range(n):
            if i+(1<<j)-1>n-1:
                break;
            t[i][j]=max(t[i][j-1],t[i+(1<<(j-1))][j-1])

def query(p,q):
    p,q=int(p),int(q)
    log=int(math.log2(q-p+1))
    m=t[p][log]
    n=t[q-(1<<log)+1][log]
    return max(m,n)

b=[-1]*(n+2)
build(n)
max1=-1
ans=0
for i in range(n):
    max1=max(max1,b[a[i]])
    b[a[i]]=i
    x=b[1]
    while x>max1:
        if x<=max1:
            break
        p=query(x,i)
        if p==i-x+1:
            ans+=1
            x=b[p+1]
        else:
            x=i-p+1
print(ans)
```