{"raw_statement":[{"iden":"statement","content":"Malnar 先生正在竞选县长，这个县一共有 $n$ 栋房屋，每栋房屋里都住着一位居民。Malnar 先生知道，选举的赢家不一定是最好的候选人，而是在选举前举办的宴会最好的候选人。因此，在选举前几天，他将邀请第 $l$ 至 $r(l\\le r)$ 栋房屋内居住的居民，为他们准备一顿丰盛的晚餐。\n\nMalnar 先生知道所有居民最喜欢吃的菜。在宴会上，他会准备大多数人喜欢的一道菜。如果一个人吃到了自己最喜欢吃的菜，将会投一票给 Malnar 先生。但是如果没有吃到自己最喜欢吃的菜，他们将会把票投给 Vlado 先生。如果没有来参加晚宴的居民，他们将会忘记选举，不做出任何投票。如果一个候选人获得了投了票的人中一半以上的人的支持，他将会赢得竞选。\n\nMalnar 先生想知道，有多少组的 $(l,r)$ 可以使他赢得竞选。"},{"iden":"input","content":"第一行包含一个整数 $n$，表示房屋的数量。\n\n第二行包含 $n$ 个整数 $a_i$，表示第 $i$ 栋房屋内居民最喜欢的菜。"},{"iden":"output","content":"仅一行，输出可以使 Malnar 先生赢得竞选的 $(l,r)$ 的组数。"},{"iden":"note","content":"**【样例 2 解释】**\n\n可以使 Malnar 先生赢得竞选的 $(l,r)$ 为：$(1, 1),(2, 2),(3, 3),(1, 3)$。\n\n**【数据规模与约定】**\n\n**本题采用子任务捆绑测试。**\n\n- Subtask 1（10 pts）：$1 ≤ n ≤ 300$。\n- Subtask 2（15 pts）：$1 ≤ n ≤ 2\\times10^3$。\n- Subtask 3（15 pts）：$\\forall i\\in\\{1,2,3,\\dots,n\\},1 ≤ a_i ≤ 2$。\n- Subtask 4（70 pts）：没有额外限制。\n\n对于 $100\\%$ 的数据，$1 \\le l\\le r ≤ n ≤ 2\\times10^5,1 ≤ a_i ≤ 10^9$。\n\n**【提示与说明】**\n\n**本题分值按 COCI 原题设置，满分 $110$。**\n\n**题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T3 Izbori。**"}],"translated_statement":null,"sample_group":[["2\n1 1","3"],["3\n2 1 2","4"],["5\n2 2 1 2 3","10"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}