Cho mảng \(A\) gồm \(N\) phần tử. Hãy tìm dãy con liên tục của mảng \(A_R\), .., \(A_L\) sao cho khi sắp xếp lại dãy con ta nhận được một mảng được sắp xếp. Ví dụ với \(A = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}\) ta chỉ cần sắp xếp lại dãy con từ \(A_4,.., A_9: {30, 25, 40, 32, 31, 35}\) để có mảng được sắp.

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào \(T\) bộ test. Mỗi bộ test gồm hai dòng: dòng đầu tiên đưa vào \(N\) (\(1 \leq N \leq 10^6\)) là số phần tử của mảng \(A\); dòng tiếp theo là \(N\) số \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 10^7\)). Các số được viết cách nhau một vài khoảng trống.

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
11
10 12 20 30 25 40 32 31 35 50 60
9
0 1 15 25 6 7 30 40 50

4 9
3 6