icpc.c

#include <stdio.h>

int main() {
    long long t;
    scanf("%lld", &t);
    while(t--) {
        long long n;
        scanf("%lld", &n);
        long long a[n+1], x, sum = 0;
        a[0] = 0;
        for (long long i = 1; i <= n; i++) 
        {
            scanf("%lld", &x);
            a[i] = a[i - 1] + x;
            sum += x;
        }
        long long ans = 0;
        long long xx = 0;
        for (long long r = 1; r <= n; r++)
        {
            long long j = (r * r) + r - a[r];
            long long w = r + a[r-1] - (r * r);
            if (w > xx)xx = w;
            long long gain = xx + j;
            if (gain > ans)ans = gain;
        }

        printf("%lld\n", sum + ans);
    }

    return 0;
}