For problem statement at 1000-1999/1900-1999/1950-1959/1956/problemD.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1950-1959/1956/verifierD.go ends with test 1 failed
input:
3
4 7 8

expected final sum:
19
obtained final sum:
3
output:
19 6
1 1
1 1
2 2
2 2
3 3
3 3
exit status 1 can you fix the verifier?  package main

import (
	"fmt"
	"math"
)

var ops [][2]int
var a []int

func mexSegment(l, r int) int {
	seen := make(map[int]bool)
	for i := l; i <= r; i++ {
		seen[a[i]] = true
	}
	m := 0
	for seen[m] {
		m++
	}
	return m
}

func makeUniform(l, r, val int) {
	if l == r {
		if val == 0 {
			if a[l] != 0 {
				ops = append(ops, [2]int{l + 1, r + 1})
				a[l] = 0
			}
		} else {
			if a[l] != 1 {
				if a[l] == 0 {
					ops = append(ops, [2]int{l + 1, r + 1})
					a[l] = 1
				} else {
					ops = append(ops, [2]int{l + 1, r + 1})
					a[l] = 0
					ops = append(ops, [2]int{l + 1, r + 1})
					a[l] = 1
				}
			}
		}
		return
	}
	if val == 0 {
		for i := l; i <= r; i++ {
			makeUniform(i, i, 1)
		}
	} else {
		build(l, r, val)
	}
	ops = append(ops, [2]int{l + 1, r + 1})
	x := mexSegment(l, r)
	for i := l; i <= r; i++ {
		a[i] = x
	}
}

func build(l, r, m int) {
	if m == 0 {
		return
	}
	if m == 1 {
		makeUniform(l, l, 0)
		return
	}
	lenPrev := 1 + (m-2)*(m-1)/2
	build(l, l+lenPrev-1, m-1)
	makeUniform(l+lenPrev, r, m-1)
}

func solve(l, r int, choice [][]int, f []int) {
	if l > r {
		return
	}
	if choice[l][r] == 0 {
		m := f[r-l+1]
		build(l, r, m)
		ops = append(ops, [2]int{l + 1, r + 1})
		x := mexSegment(l, r)
		for i := l; i <= r; i++ {
			a[i] = x
		}
	} else {
		k := choice[l][r] - 1
		solve(l, k, choice, f)
		solve(k+1, r, choice, f)
	}
}

func main() {
	var n int
	fmt.Scan(&n)
	a = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}

	f := make([]int, n+1)
	for k := 1; k <= n; k++ {
		f[k] = int((1 + math.Sqrt(float64(8*k-7))) / 2)
	}

	dp := make([][]int, n)
	choice := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		choice[i] = make([]int, n)
		if a[i] > 1 {
			dp[i][i] = a[i]
		} else {
			dp[i][i] = 1
		}
		choice[i][i] = 0
	}

	for length := 2; length <= n; length++ {
		for l := 0; l+length-1 < n; l++ {
			r := l + length - 1
			best := length * f[length]
			bestChoice := 0
			for k := l; k < r; k++ {
				val := dp[l][k] + dp[k+1][r]
				if val > best {
					best = val
					bestChoice = k + 1
				}
			}
			dp[l][r] = best
			choice[l][r] = bestChoice
		}
	}

	solve(0, n-1, choice, f)

	fmt.Printf("%d %d\n", dp[0][n-1], len(ops))
	for _, op := range ops {
		fmt.Printf("%d %d\n", op[0], op[1])
	}
}