思路

差分。原数组与差分数组一一对应，因此要使原数组全部变成零，等价于将差分数组全部变成零。考虑原操作在差分数组上的等价操作：

1. $b_1 \text{-=} 1, b_j \text{+=} 1, j \in [2, n + 1]$。
2. $b_i \text{-=} 1, i \in [1, n], b_{n + 1} \text{+=} 1$。
3. $b_1 \text{+=} 1, b_{n + 1} \text{-=} 1$。

记 $b[2, n]$ 中正数的和为 $pos$，负数绝对值的和为 $neg$。要使 $b[2, n]$ 中的负数变为零，只能使用操作一，需要操作 $neg$ 次，此后 $b_1$ 变成 $b_1 - neg$。

1. 若 $b_1 = neg$，则此时 $b_1 = 0$。现在要做的是把 $b[2, n]$ 中的正数变为零，只能使用操作二，需要操作 $pos$ 次。现在，$b[1, n]$ 已经全部为零，操作结束。
2. 若 $b_1 > neg$，则此时 $b_1 > 0$。要使 $b_1 = 0$，可以选择操作一或操作二，需要操作的最少次数都等于 $b_1$。接着，要把 $b[2, n]$ 中的正数变为零，只能使用操作二，需要操作 $pos$ 次。现在，$b[1, n]$ 已经全部为零，操作结束。
3. 若 $b_1 < neg$，则此时 $b_1 < 0$。要使 $b_1 = 0$，只能使用操作三，需要操作 $-b_1$ 次。接着，要把 $b[2, n]$ 中的正数变为零，只能使用操作二，需要操作 $pos$ 次。现在，$b[1, n]$ 已经全部为零，操作结束。

综上，最少操作次数等于 $pos + neg + abs(b_1 - neg)$。

时间复杂度 $O(n)$。

#include <iostream>
#include <vector>

#define endl "\n"

using namespace std;
using LL = long long;

void solve() {
  int n;
  cin >> n;

  vector<LL> b(n + 2);
  for (int i = 1, x; i <= n; i++) {
    cin >> x;
    b[i] += x;
    b[i + 1] -= x;
  }

  LL pos = 0, neg = 0;
  for (int i = 2; i <= n; i++)
    if (b[i] > 0) pos += b[i];
    else if (b[i] < 0) neg -= b[i];

  cout << (pos + neg + abs(b[1] - neg)) << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}