P12675 「LAOI-8」Boundary

You are given a permutation $A$ of length $n$, meaning that $A$ contains all positive integers from $1$ to $n$ exactly once. You can perform the following two operations: 1. Increase $A_i$ by $1$, at a cost of $1$. 2. Select an interval $[l, r]$ such that $A_l = A_r$ and $l \ne r$, and set all elements in that interval to $-10^9$, at a cost equal to the length of the interval. Note: Operation two can still be applied even if $A_l = A_r = -10^9$. Your task is to **turn all elements in the array $A$ into $-10^9$ with the minimum total cost**.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: * The first line contains an integer $n$, representing the length of the permutation $A$. * The second line contains $n$ integers, representing the permutation $A$.

Output $T$ lines in total. Each line contains a single integer — the minimum cost for that test case.

### Explanation For the first test case: * Increase $A_1$ by $1$: cost $1$. * Apply operation 2 on interval $[1, 3]$: cost $3$. Total cost: $1 + 3 = 4$ (this is optimal). For the second test case: * Increase $A_1$ and $A_8$ by $1$: cost $2$. * Apply operation 2 on intervals $[1, 2]$ and $[8, 9]$: cost $2 + 2 = 4$. * Apply operation 2 on interval $[2, 8]$: cost $7$. Total cost: $2 + 4 + 7 = 13$ (this is optimal). ### Constraints **Subtasks are used in this problem.** | Subtask | $n,\sum n$| Special Properties | Score | | :-----: | :-----------------------: | :--------------------------: | :----: | | $1$ | $\le 12$ | None | $10$ | | $2$ | $\le 10^6$ | $A$ is strictly increasing | $15$ | | $3$ | $\le 5000$ | None | $35$ | | $4$ | $\le 10^6$ | None | $40$ | For all test cases, it is guaranteed that $1 \le T \le 100$, $2 \le n,\sum n \le 10^6$, $1 \le A_i \le n$.