Background

The testdata for this problem has been fixed.

Problem Description

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$.

Input Format

The first line contains an integer $n$, denoting the length of $A$.

The second line contains $n$ integers, denoting $\{A_n\}$.

Output Format

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

8
3 2 1 2 3 -1 3 3

2

Hint

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