Problem Description

Hint: At the end of the statement, we provide a brief and formal description.

City A is a rainy city with many mountain streams and springs. Because people love water, they built a large fountain in the center of the city.

In the fountain pool, there is a row of $n$ stone pillars, numbered from left to right as $1, 2, \cdots , n$. The height of the $i$-th pillar is $h_i$. The pool contains water, and the water level $L$ is a positive real number. The $i$-th pillar produces a reflection with height $h'_i = 2L - h_i$. If the pillar is above the water surface, the reflection is below the water surface; if the pillar is below the water surface, the reflection is above the water surface; if the top of the pillar is exactly on the water surface, then the reflection is also exactly on the water surface.

It is said that spring spirits live in the water. On every full moon night, they dance on the pillars, following these rules:

• A spring spirit can only stay on the top of a pillar, or on the top of the pillar’s reflection. That is, if the spirit is on pillar $u$, its height $r_u$ can only be $h_u$ or $h'_u$.
• Each move, the spring spirit can only go to the adjacent pillar on the right (or the adjacent reflection).
• During the movement, the spirit’s height must be strictly increasing.

A spring spirit chooses a pillar (or its reflection) as the starting point, makes several moves, and then stops. Such a process is called a dance.

City A has a long rainy season. Because rainfall is irregular, the fountain’s water level may change many times, and the possible dance paths change as well. As a traveler from afar, you want to know how many dances can be made possible. Specifically, you need to count how many pairs $(u, v)$ ($1 \le u < v \le n$) satisfy that there exists a water level $L$ such that, in a single dance, the spirit can start from the $u$-th pillar (or its reflection) and reach the $v$-th pillar (or its reflection).

Formal: Given a positive integer sequence $h_1, h_2,\cdots , h_n$ of length $n$, find the number of pairs $(u, v)$ that satisfy all of the following conditions:

• $1 \le u < v \le n$, and $u, v$ are integers.
• There exists a positive real number $L$ and a sequence $r_u, r_{u+1},\cdots , r_v$ of length $(v - u + 1)$ such that all of the following hold:
• $\forall u \le i \le v$, let $h'_i = 2L - h_i$. Then $r_i \in \{h_i,h'_i\}$. In particular, when $h_i = h'_i$, we have $r_i = h_i$.
• $\forall u \le i < v, r_i < r_{i+1}$.

Input Format

The first line contains a positive integer $n$, representing the number of stone pillars.

The second line contains $n$ positive integers $h_1, h_2, \cdots , h_n$, representing the heights of the pillars.

Output Format

Output one line containing one integer, representing the number of pairs $(u, v)$ that satisfy the statement.

4
1 3 2 4

6

Hint

Explanation for Sample 1

All $\binom{4}{2}=6$ pairs $(u, v)$ are feasible.
For $u = 1, v = 4$, you can choose $L = 2.5$, then the sequence $h'$ is $\{4, 2, 3, 1\}$. Taking the sequence $r$ as $\{1, 2, 3, 4\}$ satisfies all conditions.

Constraints

For all testdata, $2\leq n\leq 5\times 10 ^ 5$, $1\leq h_i\leq 10 ^ {12}$.

Translated by ChatGPT 5