```go
package main

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

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

	var n int
	if _, err := fmt.Fscan(in, &n); err != nil {
		return
	}

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &a[i])
	}

	dp := make([]int, n+1)
	choice := make([]int, n+1)

	for i := 1; i <= n; i++ {
		dp[i] = dp[i-1] + a[i-1]
		choice[i] = 0
		for j := 1; j <= i; j++ {
			val := dp[j-1] + (i-j+1)*(i-j+1)
			if val > dp[i] {
				dp[i] = val
				choice[i] = j
			}
		}
	}

	var segments [][2]int
	curr := n
	for curr > 0 {
		if choice[curr] == 0 {
			curr--
		} else {
			segments = append(segments, [2]int{choice[curr], curr})
			curr = choice[curr] - 1
		}
	}

	var ops [][2]int

	getMex := func(arr []int, l, r int) int {
		has := make([]bool, 20)
		for i := l; i <= r; i++ {
			if arr[i] < 20 {
				has[arr[i]] = true
			}
		}
		mex := 0
		for has[mex] {
			mex++
		}
		return mex
	}

	applyOp := func(arr []int, l, r, val int) {
		for i := l; i <= r; i++ {
			arr[i] = val
		}
	}

	zeroOutRobust := func(arr []int, l, r int) {
		allZero := true
		for i := l; i <= r; i++ {
			if arr[i] != 0 {
				allZero = false
				break
			}
		}
		if !allZero {
			mex := getMex(arr, l, r)
			ops = append(ops, [2]int{l + 1, r + 1})
			applyOp(arr, l, r, mex)
			if mex != 0 {
				mex = getMex(arr, l, r)
				ops = append(ops, [2]int{l + 1, r + 1})
				applyOp(arr, l, r, mex)
			}
		}
	}

	var solve0 func(l, r int)
	solve0 = func(l, r int) {
		if l == r {
			ops = append(ops, [2]int{l + 1, l + 1})
			applyOp(a, l, l, 1)
			return
		}

		for k := r - 1; k >= l; k-- {
			if k < r-1 {
				zeroOutRobust(a, l, k)
			}
			solve0(l, k)
		}

		mex := getMex(a, l, r)
		ops = append(ops, [2]int{l + 1, r + 1})
		applyOp(a, l, r, mex)
	}

	for _, seg := range segments {
		l := seg[0] - 1
		r := seg[1] - 1
		zeroOutRobust(a, l, r)
		solve0(l, r)
	}

	fmt.Fprintln(out, dp[n], len(ops))
	for _, op := range ops {
		fmt.Fprintln(out, op[0], op[1])
	}
}
```