For problem statement at 1000-1999/1600-1699/1680-1689/1687/problemD.txt this is a correct solution, but verifier at 1000-1999/1600-1699/1680-1689/1687/verifierD.go ends with case 4 failed: expected 9 got 6
exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"io"
	"math"
	"os"
	"strconv"
)

var tree []int32
var segSize int

func isqrt(x int64) int64 {
	r := int64(math.Sqrt(float64(x)))
	for (r+1)*(r+1) <= x {
		r++
	}
	for r*r > x {
		r--
	}
	return r
}

func query(node, l, r, qr int, th int32) int {
	if l > qr || tree[node] <= th {
		return -1
	}
	if l == r {
		return l
	}
	m := (l + r) >> 1
	if qr > m {
		res := query(node<<1|1, m+1, r, qr, th)
		if res != -1 {
			return res
		}
	}
	return query(node<<1, l, m, qr, th)
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	p := 0
	readInt := func() int {
		for p < len(data) && (data[p] < '0' || data[p] > '9') {
			p++
		}
		v := 0
		for p < len(data) && data[p] >= '0' && data[p] <= '9' {
			v = v*10 + int(data[p]-'0')
			p++
		}
		return v
	}

	n := readInt()
	const LIM = 2000005

	present := make([]bool, LIM)
	idxOf := make([]int32, LIM)
	vals := make([]int32, 0, n)

	maxA := 0
	last := 0
	for i := 0; i < n; i++ {
		x := readInt()
		if x > maxA {
			maxA = x
		}
		present[x] = true
		if x != last {
			idxOf[x] = int32(len(vals))
			vals = append(vals, int32(x))
			last = x
		}
	}

	next := make([]int32, maxA+2)
	sentinel := int32(maxA + 1)
	next[maxA+1] = sentinel
	for i := maxA; i >= 1; i-- {
		if present[i] {
			next[i] = int32(i)
		} else {
			next[i] = next[i+1]
		}
	}

	m := len(vals)
	if m > 1 {
		g := m - 1
		segSize = 1
		for segSize < g {
			segSize <<= 1
		}
		tree = make([]int32, segSize<<1)
		for i := 0; i < g; i++ {
			tree[segSize+i] = vals[i+1] - vals[i]
		}
		for i := segSize - 1; i >= 1; i-- {
			if tree[i<<1] > tree[i<<1|1] {
				tree[i] = tree[i<<1]
			} else {
				tree[i] = tree[i<<1|1]
			}
		}
	}

	M := int64(maxA)
	k := int64(0)

	for {
		low := isqrt(k + 2)
		if low*low < k+2 {
			low++
		}
		low--
		if low < 1 {
			low = 1
		}

		high := (isqrt(4*(k+M)-3) - 1) / 2
		if low > high {
			break
		}

		maxR := int64(-1)
		B := low*low + low + 1
		E := low*low + 2*low

		for s := low; s <= high; s++ {
			left := B - k
			if left < 1 {
				left = 1
			}
			right := E - k
			if right > M {
				right = M
			}
			if left <= right {
				a := next[int(left)]
				if a <= int32(right) {
					minVal := a
					if m > 1 {
						idx := int(idxOf[int(a)])
						if idx > 0 {
							pos := query(1, 0, segSize-1, idx-1, int32(s))
							if pos == -1 {
								minVal = vals[0]
							} else {
								minVal = vals[pos+1]
							}
						}
					}
					r := E - int64(minVal)
					if r > maxR {
						maxR = r
					}
				}
			}
			B += 2*s + 2
			E += 2*s + 3
		}

		if maxR < k {
			break
		}
		k = maxR + 1
	}

	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	w.WriteString(strconv.FormatInt(k, 10))
	w.Flush()
}