In preparation for an upcoming election, Najya has polled of her friends on whether they decide on voting for candidate or candidate . In her poll, she learned that the th friend is a supporter of candidate . Being a supporter of candidate , she wants to know how many ways she can remove any number of people (possibly none) from the beginning and then remove any number of people (possibly none) from the end of her list such that a **majority** of her remaining friends are supporters of candidate .

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [30%]

##### Subtask 2 [60%]

No additional constraints.

#### Input Specification

The first line contains a single integer, .

The second line contains space-separated integers, .

#### Output Specification

Output one integer, the number of ways she can remove people from her list such that a majority of her remaining friends are supporters of candidate .

#### Sample Input

```
5
1 2 2 1 2
```

#### Sample Output

`2`

#### Sample Input 2

```
7
1 2 1 1 1 2 1
```

#### Sample Output 2

`22`

## Comments