P10144 [WC2024] Water Mirror

**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$. There is water stored in the pool, and the water level $L$ is a **positive real number**. The $i$-th pillar will form an image with height $h'_i = 2L - h_i$. If the pillar is above the water surface, its image is below the water surface; if the pillar is below the water surface, its image is above the water surface; if the top of the pillar coincides with the water surface, then its image also coincides with the water surface. It is said that spring spirits live in the water. 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 image. That is, if a spring spirit is on pillar $u$, its height $r_u$ can only be $h_u$ or $h'_u$. - Each time, a spring spirit can only move to the adjacent pillar on the right (or the image of that pillar). - During movement, the spirit’s height must be **strictly increasing**. A spring spirit chooses a pillar (or its image) as the start, 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 accordingly. As a traveler from afar, you want to know how many dances are possible. Specifically, you need to compute how many pairs $(u, v)$ ($1 \le u < v \le n$) satisfy that there exists a water level $L$ such that, in one dance, a spring spirit can start from the $u$-th pillar (or its image) and reach the $v$-th pillar (or its image). **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: - $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$, then $r_i = h_i$. - $\forall u \le i < v, r_i < r_{i+1}$.

The first line contains a positive integer $n$, indicating the number of stone pillars. The second line contains $n$ positive integers $h_1, h_2, \cdots , h_n$, indicating the heights of the pillars.

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

**Sample 1 Explanation** 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\le n\le 5\times 10^5$. - $\forall 1\le i\le n,1\le h_i\le 10^{12}$. | Test Point ID | $n\le$ | | :----------: | :----------: | | $1\sim 2$ | $10$ | | $3\sim 4$ | $100$ | | $5\sim 6$ | $400$ | | $7\sim 11$| $4000$ | | $12\sim 13$ | $5\times 10^4$ | | $14\sim 16$ | $10^5$ | | $17\sim 19$ | $2\times 10^5$ | | $20\sim 25$ | $5\times 10^5$ | Translated by ChatGPT 5