提示：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

A 城是一座多雨的城市，山溪泉水众多。出于对水的喜爱，市民们在城市中央修建了一座大喷泉。

喷泉的水池中有一排 $n$ 个石柱，从左到右编号为 $1,2,\cdots ,n$，第 $i$ 个石柱的高度为 $h_i$。水池中有储水，水位 $L$ 为一个正实数。第 $i$ 个石柱会产生一个高度为 $h_i^{\prime }=2L-h_i$ 的像。若石柱在水面上方，像在水面下方；若石柱在水面下方，像在水面上方；若石柱顶端与水面重合，则像也与水面重合。

传说水中栖息着泉水精灵，每到满月之夜，它们就会在石柱上起舞，行动规则如下：

• 泉水精灵只能栖息在石柱顶端，或者石柱的像的顶端。即如果泉水精灵在石柱 $u$ 上，它的高度 $r_u$ 便只有 $h_u,h_u^{\prime }$ 两种可能取值。
• 泉水精灵每次只能前往右侧相邻的石柱（或石柱的像）。
• 在移动过程中，泉水精灵的高度必须严格单调递增。

泉水精灵会选择一个石柱（或石柱的像）为起点，进行若干次移动后停止。这样的过程称为一次舞蹈。

A 城的雨季漫长，由于不规律的降雨，喷泉的水位可能会多次变化，舞蹈路径的可能性也随之改变。作为远道而来的旅人，你很想知道有多少种舞蹈是可能实现的。具体地，你需要计算有多少对 $(u,v)$（$1\le u<v\le n$），满足存在一种水位 $L$，使得泉水精灵在一次舞蹈中，能从第 $u$ 个石柱（或它的像）出发，到达第 $v$ 个石柱（或它的像）。

形式化的：给定一个长度为 $n$ 的正整数序列 $h_1,h_2,\cdots ,h_n$，求满足以下所有条件的 二元组 $(u,v)$ 的数量： - $1\le u<v\le n$，且 $u,v$ 为整数； - 存在一个正实数 $L$ 以及一个长度为 $(v-u+1)$ 的序列 $r_u,r_{u+1},\cdots ,r_v$ 满足以下 所有条件： - $\mathrm{\forall }u\le i\le v$，记 $h_i^{\prime }=2L-h_i$，则 $r_i\in \{h_i,h_i^{\prime }\}$，特别地，当 $h_i=h_i^{\prime }$ 时，$r_i=h_i$； - $\mathrm{\forall }u\le i<v,r_i<r_{i+1}$。

输入格式

输入的第一行包含一个正整数 $n$，表示石柱的个数。

输入的第二行包含 $n$ 个正整数 $h_1,h_2,\cdots ,h_n$，表示石柱的高度。

输出格式

输出一行一个整数，表示符合题目描述的 $(u,v)$ 对数。

样例 1

input

4
1 3 2 4

output

6

所有 $(\genfrac{}{}{0ex}{}{4}{2})=6$ 种 $(u,v)$ 都是可行的。 对于 $u=1,v=4$，可以选择 $L=2.5$，则序列 $h^{\prime }$ 为 $\{4,2,3,1\}$，取序列 $r$ 为 $\{1,2,3,4\}$ 可以满足所有条件。

数据范围

对于所有测试点，$2\le n\le 5\times {10}^5$，$1\le h_i\le {10}^{12}$。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$