```go
package main

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

const inf int64 = 1<<62

func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}
func max64(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func solveCase(a []int64) int64 {
	n := len(a)
	var dp0, dp1 int64 = 0, inf // dp0: odd (peak) at i, dp1: even (valley) at i (1-indexed)
	var x0, x1 int64 = 0, 0     // resulting value at i for each state
	for i := 1; i <= n; i++ {
		v := a[i-1]
		ndp0, ndp1 := inf, inf
		var nx0, nx1 int64

		// transition to peak at i (odd in pattern)
		// from peak at i-1: just set ai = v
		if dp0 < ndp0 {
			ndp0 = dp0
			nx0 = v
		}
		// from valley at i-1: need x_prev < v => if not, decrease v
		need := max64(0, x1-v+1)
		cost := dp1 + need
		val := v - need
		if cost < ndp0 {
			ndp0 = cost
			nx0 = val
		}

		// transition to valley at i (even in pattern)
		// from valley at i-1:
		if dp1 < ndp1 {
			ndp1 = dp1
			nx1 = v
		}
		// from peak at i-1: need x_prev > final; can set using op1 then decrease
		// choose base = max(v, x0), then decrease to < x0
		base := max64(v, x0)
		need2 := max64(0, base-x0+1)
		cost2 := dp0 + need2
		val2 := base - need2
		if cost2 < ndp1 {
			ndp1 = cost2
			nx1 = val2
		}

		dp0, dp1 = ndp0, ndp1
		x0, x1 = nx0, nx1
	}
	if n%2 == 1 {
		return dp0
	}
	return dp1
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)
	for ; t > 0; t-- {
		var n int
		fmt.Fscan(in, &n)
		a := make([]int64, n)
		for i := 0; i < n; i++ {
			fmt.Fscan(in, &a[i])
		}
		fmt.Fprintln(out, solveCase(a))
	}
}
```