Note: We provide a brief, formal description of the problem at the end of the problem statement.

City A is a rainy city with many mountain streams and springs. Out of their love for water, the citizens built a large fountain in the center of the city.

There is a row of $n$ stone pillars in the fountain's pool, numbered $1, 2, \dots, n$ from left to right, where 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 an image with a height of $h'_i = 2L - h_i$. If the pillar is above the water surface, the image is below the water surface; if the pillar is below the water surface, the image is above the water surface; if the top of the pillar coincides with the water surface, the image also coincides with the water surface.

Legend has it that spring spirits inhabit the water. On every full moon night, they dance on the stone pillars, following these rules:

• A spring spirit can only inhabit the top of a stone pillar or the top of its image. We denote the position of a spring spirit at pillar $u$ with height $r_u$ as the tuple $(u, r_u)$, where $r_u$ can only take one of two values: $h_u$ or $h'_u$.
• A spring spirit can only move to the adjacent pillar (or its image) to the right at each step.
• During the movement, the height of the spring spirit must be strictly monotonically increasing.

A spring spirit chooses a pillar (or its image) as a starting point and stops after making several moves. Such a process is called a dance.

The rainy season in City A is long. Due to irregular rainfall, the water level of the fountain may change multiple times, and the possibilities for dance paths change accordingly. As a traveler from afar, you want to know how many dances are possible. Specifically, you need to calculate how many pairs $(u, v)$ ($1 \le u < v \le n$) exist such that there is a water level $L$ where a spring spirit can travel from the $u$-th pillar (or its image) to the $v$-th pillar (or its image) in one dance.

Formal description: Given an integer sequence $h_1, h_2, \dots, h_n$ of length $n$, find the number of tuples $(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}, \dots, r_v$ of length $(v-u+1)$ satisfying all of the following conditions:
  • $\forall u \le i \le v$, letting $h'_i = 2L - h_i$, then $r_i \in \{h_i, h'_i\}$;
    • In particular, when $h_i = h'_i$, $r_i = h_i$;
  • $\forall u \le i < v, r_i < r_{i+1}$.

Input

Read the data from standard input.

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, \dots, h_n$, representing the heights of the stone pillars.

Output

Output to standard output.

Output a single integer representing the number of pairs $(u, v)$ that satisfy the problem description.

Examples

Example 1

Input

4
1 3 2 4

Output

6

Note

All $\binom{4}{2}=6$ types of $(u, v)$ are feasible.

For $u=1, v=4$, one can choose $L=2.5$, then the sequence $h'$ is $\{4, 2, 3, 1\}$, and choosing the sequence $r$ as $\{1, 2, 3, 4\}$ satisfies all conditions.

Subtasks

For all test cases, $2 \le n \le 5 \times 10^5$, $1 \le h_i \le 10^{12}$.