There arenboxes lying in a line, and initiallyi-th box is at positioni. Little Alice wants to movei-th box to positionp_i. She starts from position 1, and she can do the following operations:

1. move one step to left(right), if she can move to left(right). (i→i± 1)
2. pick up the box at current position, if she doesn't carry a box.
3. put down the box she is carrying, if there's no box at current position.
4. swap the box she is carrying and the box at current position.

Only the first operation takes one minute and Alice can carry at most one box at any time. So, find the minimum time needed for Alice to move all the boxes and go back to position 1.

There are multiple test cases. The first line of input contains an integerTindicating the number of test cases. For each test case:

The first line contains an integern(1 ≤n≤ 200000) denoting the number of boxes.

The next line containsnintegersp₁,p₂, ...,p_n(1 ≤p_i≤n). Note, {p₁,p₂, ...,p_n} is a permutation of {1, 2, ...,n}.

The sum of values ofnin all test cases doesn't exceed 4000000.

For each test case, output the minimum time needed.

2015年宁波市大学生程序设计竞赛重现赛