P10798 "CZOI-R1" Eliminating Threats

**The testdata for this problem has been fixed.**

Given a sequence $\{A_n\}$. We say an interval $[l,r]$ in sequence $A$ is a threat if and only if $1 \le l < r \le n$ and $A_l = A_r$, and $\forall i \in [l,r]$ satisfies $|A_i| \le |A_l|$. You may perform any number of operations on $A$. In each operation, choose an $A_i$ and change it to $-A_i$. What is the minimum number of **distinct** threat intervals in the final sequence $A$? Two intervals $[l_1,r_1]$ and $[l_2,r_2]$ are different if and only if $l_1 \ne l_2$ or $r_1 \ne r_2$.

The first line contains an integer $n$, denoting the length of $A$. The second line contains $n$ integers, denoting $\{A_n\}$.

The first line contains a positive integer, denoting the **minimum** number of threat intervals.

**Constraints** **This problem uses bundled tests.** - Subtask #1 ($10\text{ pts}$): $n \le 10$. - Subtask #2 ($10\text{ pts}$): $n \le 10^3$. - Subtask #3 ($10\text{ pts}$): $|A_i| \le 60$. - Subtask #4 ($10\text{ pts}$): all $|A_i|$ are equal. - Subtask #5 ($20\text{ pts}$): $n \le 10^5$. - Subtask #6 ($40\text{ pts}$): no special constraints. For $100\%$ of the testdata, $1 \le n \le 5 \times 10^5$ and $|A_i| \le 10^9$. Translated by ChatGPT 5