A Little Party Never Hurt Anybody

Axelle always wanted to be an adventurer. There are $30$ unique skills that each adventurer may possess. She entered the adventurers' guild and saw $n$ adventurers lined up. She realized that they were gathering a party to raid the boss. Each adventurer has their own value that denotes which special skills they possess:

• initially every adventurer's value is equal to $0$;

• for each skill with number $x$ that adventurer $i$ possesses, the number $2^{x-1}$ is added to his value.

A member of the party is considered to be useless if every other member of that party possesses all the skills that the useless member has. A party is considered to be bad if there is at least one useless member. A party of one member is always considered bad.

YYou are given the values of those n adventurers in the order that they are lined up in a form of array $a$. The parties may be formed only out of one consecutive segment of an array.

Your only goal is to find out how many bad parties can be formed.

Input

The first line contains an integer $n$ $(1\le n\le 10^3)$ — length of array $a$.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ $(0\le a_i<2^{30})$ — values of each adventurer in line.

Output

Output a single integer — the number of bad parties that can be formed.

Examples

Note

In the example, the bad parties are:

1. $[1]$

2. $[2]$

3. $[3]$

4. $[4]$

5. $[5]$

6. $[2,3]$ in this party, the adventurer with value $2$ is considered useless (he possesses skill with number $2$, whereas adventurer with value 3 possesses skills with numbers $1$ and $2$)

7. $[4,5]$ in this party, the adventurer with value $4$ is considered useless (he possesses skill with number $3$, whereas adventurer with value 5 possesses skills with numbers $1$ and $3$)

Scoring

1. ($5$ points): $n\le 40$;

2. ($20$ points): $n\le 100$;

3. ($33$ points): $a_i\in \{0,1\}$;

4. ($42$ points): no additional restrictions.