Dancing Fountain

A rainy metropolis A City has a grand fountain at its center. In the fountain pool, there is a row of n stone pillars numbered from 1 to n from left to right, where the i-th pillar has height \(h_i\). When the water level is set to a positive real number \(L\), each pillar produces an image with height \(h'_i = 2L - h_i\). Thus, if a pillar stands above the water, its image appears beneath the water, and vice versa. If a pillar touches the water line, its image coincides with it.

On full moon nights, the fountain sprites perform a dance on top of the pillars (or on top of their images). Their rules are as follows:

• A sprite may only stand at the top of a pillar or its image. Thus, if a sprite is on pillar i, its height \(r_i\) can be either \(h_i\) or \(h'_i\) (if \(h_i = h'_i\), then \(r_i = h_i\)).
• The sprite moves only from a pillar (or its image) to the next pillar (or its image) to the right.
• During a move, the sprite’s height must increase strictly, i.e. \(r_i < r_{i+1}\) for every move.

A dance is defined as the process in which a sprite starts from some pillar (or its image), performs several moves to the right and stops. In view of fluctuating water levels (i.e. different choices of \(L\)), the number of possible dances may change.

Your task is to determine, for a given sequence \(h_1, h_2, \dots, h_n\) of positive integers, how many ordered pairs \((u,v)\) with \(1 \le u < v \le n\) have the property that there exists a positive real number \(L\) and a sequence \(r_u, r_{u+1}, \dots, r_v\) satisfying:

• For every \(i\) from \(u\) to \(v\), if we define \(h'_i = 2L - h_i\), then \(r_i \in \{ h_i, h'_i \}\).
• For every \(i\) from \(u\) to \(v-1\), \(r_i < r_{i+1}\) (i.e. the sequence is strictly increasing).

Formal description: Given a positive integer n and a sequence of positive integers \(h_1, h_2, \dots, h_n\), count the number of pairs \((u,v)\) (with \(1\le u < v\le n\)) for which there exists a positive real number \(L\) and a choice of a sequence \(r_u, r_{u+1}, \dots, r_v\) (with each \(r_i\) equal to either \(h_i\) or \(2L-h_i\)) such that \(r_u, r_{u+1}, \dots, r_v\) is strictly increasing.

---

Observation: By choosing \(L\) sufficiently large, note that the option \(2L-h_i\) becomes very large. This forces a structure for a valid dance: one cannot switch from using \(2L-h_i\) to \(h_i\) because that would require an upper bound on \(L\). Therefore, a valid dance can be obtained by picking an index \(m\) (with \(u \le m \le v\)) where the sprite uses the original heights \(h_i\) for \(i \in [u, m]\) and uses the mirror heights \(2L-h_i\) for \(i \in [m+1, v]\). The conditions then become:

• For \(i = u, \dots, m-1\): \(h_i < h_{i+1}\).
• For \(i = m, \dots, v-1\): \(h_i > h_{i+1}\) (since \(2L-h_i h_{i+1}\)).

In other words, the subarray \(h_u, h_{u+1}, \dots, h_v\) must be unimodal (first strictly increasing then strictly decreasing; one of these parts may be empty) in order for a dance to be possible.

Your task is to count the number of pairs \((u,v)\) (with \(u<v\)) for which the segment \(h_u, h_{u+1}, \dots, h_v\) is unimodal (with at least two elements).

---

Hint: A practical approach is to precompute for every index the length of the longest contiguous strictly increasing sequence ending at that index and the longest contiguous strictly decreasing sequence starting at that index. Then, for each possible peak \(m\), the number of valid segments with \(m\) as the peak is \(\text{inc}[m] \times \text{dec}[m] - 1\) (subtracting the trivial segment of length 1). The final answer is the sum over all \(m\) from 1 to \(n\).

inputFormat

The input consists of two lines. The first line contains a single integer (n) (the number of pillars). The second line contains (n) positive integers (h_1, h_2, \dots, h_n) separated by spaces.

outputFormat

Output a single integer representing the number of pairs ((u,v)) (with (1 \le u < v \le n)) for which a valid dance is possible.

sample

2
1 2

1

</p>