Minimization of Threat Intervals

Given a sequence ({A_n}) of (n) integers, define its absolute value sequence ({|A_n|}) (which is fixed). We say that an interval ([l, r]) (with (1 \le l < r \le n)) in the sequence (A) is a threat if and only if [ A_l = A_r\quad\text{and}\quad \forall i \in [l, r], ; |A_i| \le |A_l|. ]

You are allowed to perform the following operation arbitrarily many times: choose an index (i) ((1 \le i \le n)) and replace (A_i) with (-A_i). Your task is to choose the signs of the elements (i.e. decide for each (i) whether to flip (A_i)) so that the total number of distinct threat intervals is minimized. (Two intervals ([l_1, r_1]) and ([l_2, r_2]) are considered different if (l_1 \neq l_2) or (r_1 \neq r_2).)

A key observation is that since only the sign of an element is changeable (the absolute values remain fixed), a threat interval with endpoints having absolute value (v) can only occur if both endpoints are chosen to have the same sign. Moreover, note that for ([l, r]) to be a threat, the maximum absolute value in ([l, r]) must be (|A_l|) (which equals (|A_r|)). Hence, if there are several occurrences with the same absolute value in a contiguous block (i.e. a block not separated by an element with a larger absolute value), one may assign the signs optimally to minimize the number of pairs ( (l, r) ) with (A_l = A_r).

More precisely, suppose that in such a block there are (k) positions with absolute value (v). If we assign (x) of them with one sign and (y = k-x) of them with the other sign, then the number of threat intervals from these positions is [ \binom{x}{2} + \binom{y}{2}. ] It is easy to check that this number is minimized when (|x-y| \le 1). In that case, if (k) is even the minimum number equals (\frac{k}{2}\Big(\frac{k}{2}-1\Big)), and if (k) is odd it equals (\Big(\lfloor \frac{k}{2} \rfloor\Big)^2).

To solve the problem it suffices to partition the array into segments separated by elements with a higher absolute value (which act as barriers). In each segment, considering the positions with the maximum absolute value therein, we can assign the signs to achieve the minimum internal threat intervals. Then, we recursively process the gaps between these maximum elements to account for threat intervals arising from lower values. The final answer is the sum of the minimal threat intervals computed over all these segments.

Your task is to output the minimum possible number of distinct threat intervals after optimally performing sign flips.

inputFormat

The first line contains a single integer (n) (the length of the sequence). The second line contains (n) space-separated integers (A_1, A_2, \ldots, A_n).

outputFormat

Output a single integer – the minimum number of distinct threat intervals after optimally flipping the signs.

sample

3
1 2 1

0