### 问题描述 在上大学之后， Yaya 和 Clrlss 在课上接触了一种神秘而又富有吸引力的时代产物：数据结构。这是一种用只言片语无法准确描述的东西，但是它的神奇与巧妙使得 Clrlss 和 Yaya 赞叹不已。 为了试试不同的数据结构究竟能做到什么操作，他们拿出了一个序列。这个序列一共有 $n$ 个整数，分别为 $a_{1},a_{2},...,a_{n}$ 。然后，他们要对这个序列做什么呢？这让他们犯了难。 突然， Clrlss 一拍脑门，兴奋地说：“不如我们来数一数这个序列有多少子区间，满足区间内众数的出现次数恰好超过区间长度的一半！” 由于刚刚接触数据结构， Yaya 听了这个问题之后陷入了沉思。但是， Clrlss 却已经悄悄把这个问题解决了。 亲爱的见证者啊，这种题目对您来说肯定不在话下。至于 Yaya， 让我们祝她不要思考到低血糖。 简化题意：给定一个长度为 $n$ 的序列 $a_{1}..a_{n}$ ,问存在多少个子区间 $a_{l}..a_{r}$ $(1\le l \le r \le n)$ ,满足区间众数出现的次数为$(R-L+1)/2+1$。 其中，"/" 的定义为整除并且向下取整。 ### 输入格式 第一行输入一个整数 $n$ （$1 \le n \le 10^5$） ,表示序列的长度。 第二行输入 $n$ 个整数 $a_{1},a_{2},...,a_{n}$ , 表示给定的序列 ($1 \le a_i \le 10^9$)。 ### 输出格式 一行一个整数，表示符合条件的区间个数。 ### 样例输入 ``` 6 1 1 4 5 1 4 ``` ### 样例输出 ``` 9 ``` ### 说明 合法的区间有： - 所有长度为 $1$ 的区间，共6个； - $a_{1}..a_{2}$ ， $a_{1}..a_{3}$ 以及 $a_{1}..a_{5}$ 。