Solitaire

Time limit2sMemory limit256 MB

Summary

Given the starting deck order, compute the fewest redeals needed to move every card to the goal pile using the helper as ordered storage.

Level: Medium7 of 10
Topics: Simulation, Greedy, Stack
Solved: No attempts yet

Problem

You have $N$ cards valued from $1$ to $N$ . The game starts with every card face down in the "initial" position. Three other positions hold cards face up: "goal", "helper" and "pile". A face up card can be moved only while it is on top of one of those three positions. You win once all $N$ cards are on goal in ascending order with $N$ on top.

The rules are as follows.

You may play a card onto goal only if the top card of goal is one less than the value of that card. If goal is empty, only the card with value $1$ can go there. For example, if the top card of goal is $3$ , the only card you may play onto goal is $4$ .
You may play a card onto helper only if the top card of helper is one more than the value of that card. If helper is empty, only the card with value $N$ can go there. For example, if the top card of helper is $8$ , the only card you may play onto helper is $7$ .
The only card you may move onto pile is the top card of the initial deck, and you turn it face up as you move it.
Once the initial deck is empty and the game is not finished, take all the cards from pile and turn them over onto the initial position. That stack becomes the new initial deck. The top card of pile becomes the bottom card of the new initial deck.

Find the minimum number of moves of type 4 needed to finish the game.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ).

Each test case consists of two lines. The first line contains the number of cards $N$ ( $1 \le N \le 1000$ ). The second line contains $N$ integers describing the initial deck. The first number is the card at the bottom of the initial deck, and the last number is the card on top, so it is the first one turned over onto pile. The sequence is a permutation of the integers from $1$ to $N$ .

Output

For each test case print the minimum number of moves of type 4 needed to win the game, one per line.

Examples2

Example 1
Input
```
2
3
1 2 3
6
6 2 4 3 5 1
```
Expected output
```
0
1
```
Example 2
Input
```
3
1
1
2
1 2
2
2 1
```
Expected output
```
0
0
0
```