fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int M = 262144 + 5;
  5. int A[M];
  6.  
  7. pair<int, int> check(int l, int r) {
  8. if (l + 1 == r) {
  9. if (A[r] % 2 == 0) {
  10. if (A[l] + 1 == A[r]) return {0, A[r]};
  11. } else {
  12. if (A[l] - 1 == A[r]) return {1, A[l]};
  13. }
  14. return {-1, -1};
  15. }
  16. int mid = l + (r - l) / 2;
  17. pair<int, int> a = check(l, mid);
  18. pair<int, int> b = check(mid + 1, r);
  19. if (a.first == -1 || b.first == -1) return {-1, -1};
  20. int c = min(a.second, b.second);
  21. int d = max(a.second, b.second);
  22.  
  23. int sz = r - l + 1;
  24. if (c != d - sz / 2) return {-1, -1};
  25.  
  26.  
  27. return {a.first + b.first + (a.second > b.second), max(a.second, b.second)};
  28. }
  29.  
  30. void solve() {
  31. int m;
  32. cin >> m;
  33. for (int i = 0; i < m; i++) cin >> A[i];
  34. if (m == 1) cout << 0 << endl;
  35. else cout << check(0, m - 1).first << endl;
  36. }
  37.  
  38. int main() {
  39. int t;
  40. cin >> t;
  41. while (t--) solve();
  42. }
Success #stdin #stdout 0.01s 5288KB
stdin
4
8
6 5 7 8 4 3 1 2
4
3 1 4 2
1
1
8
7 8 4 3 1 2 6 5
stdout
4
-1
0
-1