DMOPC '19 Contest 3 P3 - Majority

View as PDF

Submit solution

Points: 12
Time limit: 1.4s
Memory limit: 128M

Author:
Problem type

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 ith 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) end of her list such that a majority of her remaining friends are supporters of candidate 1.

Constraints

1 \leq N \leq 150\space 000
v_i\in \{1,2\}

Subtask 1 [10%]

1 \leq N\leq 100

Subtask 2 [30%]

1 \leq N\leq 2000

Subtask 2 [60%]

No additional constraints.

Input Specifications

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

Output Specifications

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

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

There are no comments at the moment.