Description

给定一个长度为 $n$ 的整数数组 $a = (a_1, a_2, \dots, a_n)$。

你需要计算有多少个长度为奇数的区间 $[l, r]$（$1 \le l \le r \le n$，$r - l + 1$ 为奇数），满足以下条件：

设该区间的中点为位置 $m = \frac{l + r}{2}$；

该区间的中位数值等于 $a_m$，即该区间排序后第 $\frac{r - l + 2}{2}$ 小的元素等于 $a_m$。

换句话说，你需要统计有多少个奇数长度的区间，其中点元素的值正好是该区间的中位数。

Format

Input

第一行包含一个整数 $n$（$1 \le n \le 1.2*10^4$）——数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组的元素。

Output

输出一个整数，表示满足条件的区间数量。

Samples

5
1 2 3 4 5

9