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.


-----Input-----

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.


-----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]$.

Difficulty: interview

Starter code:

Solutions:
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)

#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)