Mr. Malnar is running for mayor of the Tompojevci county. The Tompojevci
county consists of a single village (called Tompojevci), made up of a row of \(n\)
houses labeled with integers from 1 to \(n\). In each house there is one resident, but
more importantly for Mr. Malnar, a voter. Mr. Malnar knows that the election
isn’t won by the best candidate, but by the candidate who hosts the best banquet
before the election. Therefore, a few days before the election he will organize a
banquet. He’ll invite all residents of the village who live at houses whose number
is between \(l\) and \(r\) (\(l \le r\)) inclusive and prepare a delicious meal for them.
Mr. Malnar knows all the residents of Tompojevci very well so he knows what the favourite dish of each
resident is. That’s why for the banquet he’ll prepare the meal that is the favourite of the majority of the
invited people. However, only the people that get their favourite meal will vote for Mr. Malnar, while
the rest will vote for the only other candidate, Mr. Vlado. To win the election, Mr. Malnar needs to get
strictly more than half of the votes from the people that voted. The residents that weren’t invited to the
banquet will forget about the election and are not going to vote.
Mr. Malnar now wants to know how many different ways there are for him to choose the numbers \(l\) and \(r\)
so that he wins the election.

Subtask 1 (10 points): \(1 \le n \le 300\)

Subtask 2 (15 points): \(1 \le n \le 2000\)

Subtask 3 (15 points): \(1 \le a_{i} \le 2\) for all \(1 \le i \le n\)

Subtask 4 (70 points): No additional constraints.

The first line contains a positive integer \(n\) (\(1 \le n \le 200\,000\)) from the problem statement.
The second line contains \(n\) positive integers \(a@@RISE_MATH_BLOCK_0@@i \le 10^{9}\)) each representing the favourite dish of the
resident at house \(i\).

In the only line print the number of different ways for Mr. Malnar to choose the numbers \(l\) and \(r\) so that
he wins the election.

생성자가 기록되지 않았습니다.

출처 COCI 2021/2022 Contest 4