Dancing Fountain Sprite

In City A there is a famous fountain with a row of n stone pillars numbered from 1 to n. The height of the i-th pillar is (h_i). The fountain pool has water with a water level (L) (a positive real number). Each pillar produces a mirror image at height (h'i = 2L - h_i). Notice that if the pillar is above the water then its image is below the water, and vice‐versa; if the pillar’s top touches the water surface, so does its image.\n\nOn full moon nights, the spring water sprites perform a dance on the pillars. A sprite may start on the top of any pillar or on the top of its image. It moves only to the next (right‐adjacent) pillar (or its image) and, during the dance, its height (r_i) at pillar (i) (which must equal either (h_i) or (h'i)) must be strictly increasing. Formally, if a sprite starts at pillar (u) and after several moves stops at pillar (v) (with (1 \le u < v \le n)) then there exists a positive real number (L) and a sequence (r_u, r{u+1},\dots,r_v) such that for every (i) from (u) to (v), (r_i \in {h_i, 2L - h_i}) and for every (i, u \le i < v,) (r_i < r{i+1}).\n\nYour task is to count the number of ordered pairs ((u, v)) ( (1 \le u < v \le n)) for which there exists a positive real number (L) and a valid dance (i.e. a valid sequence (r_u, r_{u+1}, \dots, r_v)) satisfying the rules above.\n\nA brief formal description: Given 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 exist a positive real (L) and a sequence (r_u, r_{u+1},\dots,r_v) with the following properties:\n\n- For each (i) with (u \le i \le v), define (h'i = 2L - h_i) and require (r_i \in {h_i, h'i}) (in particular, if (h_i = h'i) then (r_i = h_i)).\n- For each (i) with (u \le i < v), (r_i < r{i+1}).\n\nIt turns out that one may show that a necessary and sufficient condition for a segment ([u,v]) (with (v \ge u+2)) to be danceable is that either the pair of endpoints forces a strict inequality when compared to the interior. More precisely, if we denote by (A = \max{h_u, h_v}) and (B = \min{h_u, h_v}), and if the interior elements (i.e. (h{u+1}, \dots, h{v-1})) have maximum (M_{\max}) and minimum (M_{\min}), then the dance is possible if and only if (A > M_{\max}) or (B < M_{\min}). (All segments of length 2 are always danceable.)\n\nDetermine the number of valid pairs ((u,v)).

inputFormat

The first line contains a single integer (n) ((1 \le n \le 2000)). The second line contains (n) positive integers (h_1, h_2, \dots, h_n) separated by spaces.

outputFormat

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

sample

3
2 3 2

2