package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 1024*1024)
	scanner.Buffer(buf, 1024*1024)

	scanInt := func() int64 {
		scanner.Scan()
		res, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		return res
	}

	scanner.Scan()
	t, _ := strconv.Atoi(scanner.Text())

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for i := 0; i < t; i++ {
		n := scanInt()
		var sum int64 = 0
		var maxG int64 = -2000000000000000000
		var bestChange int64 = 0
		var p int64 = 0

		for j := int64(1); j <= n; j++ {
			a := scanInt()

			g := -j*j + j + p
			if g > maxG {
				maxG = g
			}

			p += a
			sum += a

			f := j*j + j - p
			change := f + maxG
			if change > bestChange {
				bestChange = change
			}
		}
		fmt.Fprintln(out, sum+bestChange)
	}
}