1.2 KiB
1.2 KiB
选举3
题目描述
你在竞选魔法学校的校长，有 n 位同学每人一票，已知每人的选择 $a[i]$，代表第 i 位同学支持第 a[i] 位候选人。
选举方式如下：选择一个连续区间 [l,r] ，对 a[l,...,r] 进行计票（区间外的人不管），若有候选人获得其中严格多于一半的选票（严格众数），则这个人当选，否则没人当选。
现在想知道的是有多少种不同方法选择区间 $[l,r]$，使得有人当选。
输入格式
第一行1个整数 n
第二行 n 个整数 a[1...n]
输出格式
输出1个整数代表答案
样例 #1
样例输入 #1
2
1 1
样例输出 #1
3
样例 #2
样例输入 #2
3
2 1 2
样例输出 #2
4
样例 #3
样例输入 #3
5
2 2 1 2 3
样例输出 #3
10
样例 #4
样例输入 #4
见下发样例
样例输出 #4
提示
对于所有数据，满足 1\le n \le 2\times 10^5, 1\le a[i] \le 10^9
子任务1（10分）：n\le 300
子任务2（15分）：n\le 2000
子任务3（20分）：a[i]\le 2
子任务4（55分）：无特殊限制