Problem Description

Mr. Malnar is running for mayor, and there are $n$ houses in this town, each housing a single resident. Mr. Malnar knows that the winner of the election is not necessarily the best candidate but the one who throws the best pre-election party. Therefore, a few days before the election, he will invite the residents living in houses from $l$ to $r$ (where $l \le r$) to a lavish dinner.

Mr. Malnar is aware of everyone's favorite dish. At the party, he will prepare the dish that most people like. If a person eats their favorite dish, they will vote for Mr. Malnar. However, if they do not eat their favorite dish, they will vote for Mr. Vlado. Residents who do not attend the dinner will forget about the election and will not cast any votes. If a candidate receives more than half of the votes from those who voted, he will win the election.

Mr. Malnar wants to know how many pairs $(l, r)$ can ensure his victory in the election.

Input Format

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

The second line contains $n$ integers $a_i$, representing 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 ensure Mr. Malnar's victory in the election.

Sample Input and Output

Input Sample #1

2
1 1

Output Sample #1

3

Input Sample #2

3
2 1 2

Output Sample #2

4

Input Sample #3

5
2 2 1 2 3

Output Sample #3

10

Notes/Hints

[Sample 2 Explanation]

The pairs $(l, r)$ that can ensure Mr. Malnar's victory are: $(1, 1), (2, 2), (3, 3), (1, 3)$.

[Data Range and Constraints]

This problem is tested with subtask binding.

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

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

[Score and Origin]

This problem's score is set according to the original COCI contest, with a full score of $110$.

The problem is translated from COCI2021-2022 CONTEST #4 T3 Izbori.

见题面 Input 部分

见题面 Output 部分