Election Dinner Winning Strategy

Malnar is running for county governor. In his county there are \(n\) houses, with exactly one resident in each house. Each resident has a favorite dish. A few days before the election, Malnar invites all residents living in houses numbered from \(l\) to \(r\) (with \(1 \le l \le r \le n\)) to a sumptuous dinner. At the dinner, he prepares a single dish – specifically, the dish that is favored by the majority of the invited residents. (A dish is considered to enjoy majority if its frequency is strictly more than \(\frac{r-l+1}{2}\).)

If an invited resident eats their favorite dish, they cast their vote for Malnar; otherwise, they vote for his opponent Vlado. Residents who are not invited do not vote at all. Malnar wins the election if he obtains more than half of the total votes cast by the invited residents. In other words, if the majority dish occurs more than \(\frac{r-l+1}{2}\) times in the dinner, then Malnar wins that invitation.

Your task is to compute the number of pairs \((l,r)\) (with \(1 \le l \le r \le n\)) for which the invited residents have a majority dish, i.e. a dish that appears more than half the times in the subarray \(a[l\ldots r]\). Each such pair guarantees Malnar wins the election.

inputFormat

The first line contains a single integer \(n\) representing the number of houses. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), where \(a_i\) is the favorite dish of the resident in the \(i\)-th house.

outputFormat

Output a single integer: the number of pairs \((l,r)\) for which there exists a dish that appears more than \(\frac{r-l+1}{2}\) times in the subarray \(a[l...r]\).

sample

3
1 2 3

3