In preparation for an upcoming election, Najya has polled ~N~ of her friends on whether they decide on voting for candidate ~1~ or candidate ~2~. In her poll, she learned that the ~i^\text{th}~ friend is a supporter of candidate ~v_i~. Being a supporter of candidate ~1~, 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 ~1~.

Constraints

~1 \le N \le 150\,000~
~v_i \in \{1,2\}~

Subtask 1 [10%]

~1 \le N \le 100~

Subtask 2 [30%]

~1 \le N \le 2000~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains a single integer, ~N~.
The second line contains ~N~ space-separated integers, ~v_1, v_2, \dots, v_N~.

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 ~1~.

Sample Input 1

5
1 2 2 1 2

Sample Output 1

2

Sample Input 2

7
1 2 1 1 1 2 1

Sample Output 2

22