#include using namespace std; const int MAXN = (int) 1e5 + 5; int a[MAXN], leftX[MAXN], rightX[MAXN]; int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } int desiredHeight = 0; int min_val1 = (int) 2e9; for (int i = 0; i < n; i++) { // x, here // 1 2 .. (x - 1), x, (x - 1) .. 1. // hi_x = min(i + 1, n - i) // for j < i, a[j] >= x - (i - j) // i.e. a[j] - j >= x - i. // x <= a[j] - j + i. int y = min(a[i], min_val1 + i); leftX[i] = y; min_val1 = min(min_val1, a[i] - i); } int min_val2 = (int) 2e9; for (int i = n - 1; i >= 0; i--) { // for j > i, a[j] >= x - (j - i). // a[j] + j - i >= x int z = min_val2 - i; rightX[i] = z; min_val2 = min(min_val2, a[i] + i); } for (int i = 0; i < n; i++) { int x = min(i + 1, n - i); x = min(x, leftX[i]); x = min(x, rightX[i]); desiredHeight = max(desiredHeight, x); } assert(desiredHeight >= 0); long long sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; } //cerr << "desiredHeight " << desiredHeight << endl; long long remove = desiredHeight; desiredHeight--; while (desiredHeight >= 0) { remove += 2 * desiredHeight; desiredHeight--; } //cerr << "sum " << sum << " " << remove << endl; sum -= remove; printf("%lld\n", sum); } return 0; }