「CZOI-R1」消除威胁

**本题数据已修复。**

给定一个序列 $\{A_n\}$。 我们称序列 $A$ 中的一个区间 $[l,r]$ 具有威胁，当且仅当 $1\le l<r\le n$ 且 $A_l=A_r$，且 $\forall i\in[l,r]$ 满足 $|A_i|\le|A_l|$。 你可以操作 $A$ 任意次，每次操作选择一个 $A_i$ 修改为 $-A_i$。请问最后序列 $A$ 中具有威胁的**不同**区间**最少**有多少个？ 两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$ 不同，当且仅当 $l_1 \ne l_2$ 或 $r_1 \ne r_2$。

第一行一个整数 $n$ ，表示 $A$ 的长度。 第二行 $n$ 个整数，表示 $\{A_n\}$。

第一行一个正整数，表示**最少**的具有威胁的区间个数。

8
3 2 1 2 3 -1 3 3

2

**【数据范围】** **本题采用捆绑测试**。 - Subtask #1（$10\text{ pts}$）：$n\le10$。 - Subtask #2（$10\text{ pts}$）：$n\le10^3$。 - Subtask #3（$10\text{ pts}$）：$|A_i|\le60$。 - Subtask #4（$10\text{ pts}$）：$|A_i|$ 均相等。 - Subtask #5（$20\text{ pts}$）：$n\le10^5$。 - Subtask #6（$40\text{ pts}$）：无特殊限制。 对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$|A_i|\le10^9$。