contests/Round#809/A/B/main.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <bits/stdc++.h>

using namespace std;

bool isCool(vector<int> &a, int i) {
  if (i == 0) {
    return false;
  }
  if (a[i - 1] < a[i] && a[i + 1] < a[i]) {
    return true;
  }
  return false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
      cin >> x;
    long long ans = 0;
    long long mx = 0;
    int max_cool = (n - 1) / 2;
    int cnt = 0;
    if(n > 3) {
      for (int i = 1; i < n - 1; i++) {
        if(isCool(a,i)) {
          cnt++;
        }
        if (!isCool(a, i) && i % 2 == 0) {
          ans += abs(a[i] - max(a[i - 1], a[i + 1])) + 1;
        } else if(!isCool(a, i) && i % 2 != 0) {
          mx += abs(a[i] - max(a[i - 1], a[i + 1])) + 1;
        }
      }
      long long mx2 = 0;
      for (int i = 1; i < n - 1; i += 3) {
        if (!isCool(a, i)) {
          mx2 += abs(a[i] - max(a[i - 1], a[i + 1])) + 1;
        }
      }
      cerr << mx << " " << ans << " " << mx2 << endl;
      if(cnt < max_cool) {
        // cout << max(mx2, max(ans, mx)) << endl;
      } else {
        cout << min(mx2, min(ans, mx)) << endl;
      }

    } else {
      cout << abs(a[1] - max(a[0], a[2])) + 1 << endl;
    }
  }
}