给定一个长度为 $n$ 的整数序列 $h_1, h_2, \dots, h_n$，求满足以下所有条件的数对 $(u, v)$ 的数量：

• $1 \le u < v \le n$，且 $u, v$ 为整数；
• 存在一个正实数 $L$ 和一个长度为 $(v - u + 1)$ 的序列 $r_u, r_{u+1}, \dots, r_v$，满足以下所有条件：
  • 对于所有 $u \le i \le v$，令 $h'_i = 2L - h_i$，则 $r_i \in \{h_i, h'_i\}$；
    • 特别地，当 $h_i = h'_i$ 时，$r_i = h_i$；
  • 对于所有 $u \le i < v$，$r_i < r_{i+1}$。

输入格式

第一行包含一个正整数 $n$ ($2 \le n \le 5 \times 10^5$)，表示柱子的数量。

第二行包含 $n$ 个正整数 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^{12}$)，表示柱子的高度。

输出格式

输出一行，包含一个整数，表示满足条件的数对 $(u, v)$ 的数量。

样例

样例输入 1

4
1 3 2 4

样例输出 1

6