Problem Description

Mr. Malnar is running for county prefect. This county has $n$ houses, and each house has one resident. Mr. Malnar knows that the winner of an election is not necessarily the best candidate, but the one who holds the best banquet before the election. Therefore, a few days before the election, he will invite the residents living in houses $l$ to $r$ $(l\le r)$, and prepare them a luxurious dinner.

Mr. Malnar knows every resident’s favorite dish. At the banquet, he will prepare the dish that is liked by the majority of people. If a person gets to eat their favorite dish, they will vote for Mr. Malnar. But if they do not get to eat their favorite dish, they will vote for Mr. Vlado. Residents who do not come to the banquet will forget about the election and will not vote at all. If a candidate gets support from more than half of the people who voted, they will win the election.

Mr. Malnar wants to know how many pairs $(l, r)$ can make him win the election.

Input Format

The first line contains an integer $n$, the number of houses.

The second line contains $n$ integers $a_i$, where $a_i$ is the favorite dish of the resident in the $i$-th house.

Output Format

Output a single line containing the number of pairs $(l, r)$ that can make Mr. Malnar win the election.

2
1 1

3

3
2 1 2

4

5
2 2 1 2 3

10

Hint

Sample 2 Explanation

The pairs $(l, r)$ that can make Mr. Malnar win the election are: $(1, 1),(2, 2),(3, 3),(1, 3)$.

Constraints

This problem uses bundled subtasks.

• Subtask 1 (10 pts): $1 \le n \le 300$.
• Subtask 2 (15 pts): $1 \le n \le 2\times10^3$.
• Subtask 3 (15 pts): $\forall i\in\{1,2,3,\dots,n\},1 \le a_i \le 2$.
• Subtask 4 (70 pts): No additional constraints.

For $100\%$ of the testdata, $1 \le l \le r \le n \le 2\times10^5,1 \le a_i \le 10^9$.

Notes

The score of this problem follows the original COCI settings, with a full score of $110$.

Translated from T3 Izbori of COCI2021-2022 CONTEST #4.

Translated by ChatGPT 5