C - Sort by Queue and Reverse 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1100 点

問題文

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます．また，最初は空のキューがあります．

次の 3 種類の操作を，好きな順序で何回でも行えます．

  • 追加操作: P が空でない場合，P の先頭の要素を取り除き，その要素をキューの末尾に追加する．
  • 出力操作: キューが空でない場合，先頭の要素を取り除き，その値を出力する．
  • 反転操作: キュー内の要素の順序を反転する．つまり，現在のキューの要素が (v_1,v_2,\ldots,v_k) だった場合，これを (v_k,v_{k-1},\ldots,v_1) に置き換える．

すべての要素を出力し，出力した値が順に 1,2,\ldots,N となるようにしたいです．

これを実現することが可能かどうか判定してください．また可能な場合は，必要な反転操作の最小回数を求めてください．

1 つの入力につき，T ケースを解いてください．

制約

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • 1 \leq P_i \leq N (1 \leq i \leq N)
  • P_1,P_2,\ldots,P_N は互いに異なる．
  • T ケースにわたる N の総和は 250000 以下である．
  • 入力される数値はすべて整数である．

入力

入力は標準入力から以下の形式で与えられる．

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる．

N
P_1 P_2 \ldots P_N

出力

各テストケースについて，出力した値を順に 1,2,\ldots,N とすることが可能ならば必要な反転操作の最小回数を，不可能ならば -1 を出力せよ．

入力例 1

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

出力例 1

3
-1
0
0
1
4
1
0
-1
2

1 番目のテストケースでは，例えば次のように操作できます．

操作 操作後のキュー ここまでに出力した値
追加操作 \times 2 (3,2) なし
反転操作 (2,3) なし
追加操作 \times 2 (2,3,4,1) なし
反転操作 (1,4,3,2) なし
出力操作 (4,3,2) 1
反転操作 (2,3,4) 1
出力操作 \times 3 空 1,2,3,4

反転操作を 3 回行っています．2 回以下の反転操作で実現することはできないため，答えは 3 です．

Score : 1100 points

Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N). Additionally, there is a queue that is initially empty.

You can perform the following three types of operations any number of times, in any order.

  • Append operation: If P is not empty, remove the first element of P and add that element to the end of the queue.
  • Output operation: If the queue is not empty, remove the front element and output its value.
  • Reverse operation: Reverse the order of the elements in the queue. That is, if the elements of the queue are currently (v_1,v_2,\ldots,v_k), replace them with (v_k,v_{k-1},\ldots,v_1).

You want to output all elements so that the output values are 1,2,\ldots,N in this order.

Determine whether this is possible. If it is possible, find the minimum number of reverse operations required.

You are given T test cases; solve each of them.

Constraints

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • 1 \leq P_i \leq N (1 \leq i \leq N)
  • P_1,P_2,\ldots,P_N are pairwise distinct.
  • The sum of N over all test cases in a single input is at most 250000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
P_1 P_2 \ldots P_N

Output

For each test case, output the minimum number of reverse operations required if it is possible to make the output values 1,2,\ldots,N in this order, and -1 otherwise.

Sample Input 1

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

Sample Output 1

3
-1
0
0
1
4
1
0
-1
2

In the first test case, for example, you can perform the operations as follows.

Operation Queue after the operation Values output so far
Append operation \times 2 (3,2) None
Reverse operation (2,3) None
Append operation \times 2 (2,3,4,1) None
Reverse operation (1,4,3,2) None
Output operation (4,3,2) 1
Reverse operation (2,3,4) 1
Output operation \times 3 Empty 1,2,3,4

This performs the reverse operation 3 times. It cannot be achieved with 2 or fewer reverse operations, so the answer is 3.