题目背景

本题数据已修复。

题目描述

给定一个序列 $\{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$。