Description

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.

Input Format

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 Format

Output $T$ lines in total.

Each line contains a single integer — the minimum cost for that test case.

2
3
1 3 2
9
1 2 3 4 5 6 7 8 9

4
13

Hint

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.

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