# 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≤n≤10_{3})$ — length of array $a$.

The second line contains $n$ integers $a_{1},a_{2},…,a_{n}$ $(0≤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]$

$[2]$

$[3]$

$[4]$

$[5]$

$[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$)

$[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

($5$ points): $n≤40$;

($20$ points): $n≤100$;

($33$ points): $a_{i}∈{0,1}$;

($42$ points): no additional restrictions.