import sys
import math
from collections import Counter
from collections import defaultdict
def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()
def solve(arr):
pow = 1
ans = 0
temp = []
while 2 ** pow <= len(arr):
k = 2 ** pow
j = 0
cnt = 0
if temp:
arr = temp
temp = []
while j < len(arr):
t = []
cnt += 1
for i in range(k):
t.append(arr[j])
j += 1
if t != sorted(t):
ans += 1
t.sort()
for i in range(len(t) - 1):
if t[i+1] - t[i] != 1:
return -1
temp.extend(t)
pow += 1
return ans
t = int(input())
for _ in range(t):
n = get_ints()
arr = get_ints()
print(solve(arr))
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 300300;
int n, m;
int arr[MAXM];
int solve(int l, int r) {
if (r - l == 1) return 0;
int mid = (l + r) >> 1;
int mal = *max_element(arr + l, arr + mid);
int mar = *max_element(arr + mid, arr + r);
int ans = 0;
if (mal > mar) {
++ans;
for (int i = 0; i < (mid - l); ++i)
swap(arr[l + i], arr[mid + i]);
}
return solve(l, mid) + solve(mid, r) + ans;
}
int solve() {
int ans = solve(0, m);
if (is_sorted(arr, arr + m))
return ans;
return -1;
}
int main() {
int t; cin >> t;
while (t--) {
cin >> m;
for (int i = 0; i < m; ++i)
cin >> arr[i];
cout << solve() << endl;
}
}1630C - Paint the Middle | 1630D - Flipping Range |
1328A - Divisibility Problem | 339A - Helpful Maths |
4A - Watermelon | 476A - Dreamoon and Stairs |
1409A - Yet Another Two Integers Problem | 977A - Wrong Subtraction |
263A - Beautiful Matrix | 180C - Letter |
151A - Soft Drinking | 1352A - Sum of Round Numbers |
281A - Word Capitalization | 1646A - Square Counting |
266A - Stones on the Table | 61A - Ultra-Fast Mathematician |
148A - Insomnia cure | 1650A - Deletions of Two Adjacent Letters |
1512A - Spy Detected | 282A - Bit++ |
69A - Young Physicist | 1651A - Playoff |
734A - Anton and Danik | 1300B - Assigning to Classes |
1647A - Madoka and Math Dad | 710A - King Moves |
1131A - Sea Battle | 118A - String Task |
236A - Boy or Girl | 271A - Beautiful Year |