For problem statement at 0-999/600-699/630-639/631/problemE.txt this is a correct solution, but verifier at 0-999/600-699/630-639/631/verifierE.go ends with All tests passed can you fix the verifier? package main

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

const NegInf int64 = -1 << 60

type FastScanner struct {
	data []byte
	idx  int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data}
}

func (fs *FastScanner) NextInt64() int64 {
	n := len(fs.data)
	for fs.idx < n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
	sign := int64(1)
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	var val int64
	for fs.idx < n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int64(c-'0')
		fs.idx++
	}
	return sign * val
}

type Line struct {
	m int64
	b int64
}

func (ln Line) val(x int64) int64 {
	return ln.m*x + ln.b
}

type LiChao struct {
	xs    []int64
	lines []Line
	has   []bool
}

func NewLiChao(xs []int64) *LiChao {
	sz := 4 * len(xs)
	if sz == 0 {
		sz = 1
	}
	return &LiChao{
		xs:    xs,
		lines: make([]Line, sz),
		has:   make([]bool, sz),
	}
}

func (t *LiChao) Add(nw Line) {
	t.add(nw, 1, 0, len(t.xs)-1)
}

func (t *LiChao) add(nw Line, p, l, r int) {
	if !t.has[p] {
		t.has[p] = true
		t.lines[p] = nw
		return
	}
	mid := (l + r) >> 1
	xl, xm, xr := t.xs[l], t.xs[mid], t.xs[r]
	if nw.val(xm) > t.lines[p].val(xm) {
		t.lines[p], nw = nw, t.lines[p]
	}
	if l == r {
		return
	}
	if nw.val(xl) > t.lines[p].val(xl) {
		t.add(nw, p<<1, l, mid)
	} else if nw.val(xr) > t.lines[p].val(xr) {
		t.add(nw, p<<1|1, mid+1, r)
	}
}

func (t *LiChao) Query(x int64) int64 {
	return t.query(x, 1, 0, len(t.xs)-1)
}

func (t *LiChao) query(x int64, p, l, r int) int64 {
	res := NegInf
	if t.has[p] {
		res = t.lines[p].val(x)
	}
	if l == r {
		return res
	}
	mid := (l + r) >> 1
	if x <= t.xs[mid] {
		v := t.query(x, p<<1, l, mid)
		if v > res {
			res = v
		}
	} else {
		v := t.query(x, p<<1|1, mid+1, r)
		if v > res {
			res = v
		}
	}
	return res
}

func main() {
	fs := NewFastScanner()
	n := int(fs.NextInt64())

	a := make([]int64, n+1)
	pref := make([]int64, n+1)
	vals := make([]int64, n)
	var initial int64

	for i := 1; i <= n; i++ {
		x := fs.NextInt64()
		a[i] = x
		pref[i] = pref[i-1] + x
		initial += int64(i) * x
		vals[i-1] = x
	}

	sort.Slice(vals, func(i, j int) bool { return vals[i] < vals[j] })
	xs := make([]int64, 0, n)
	for _, v := range vals {
		if len(xs) == 0 || xs[len(xs)-1] != v {
			xs = append(xs, v)
		}
	}

	var bestDelta int64

	leftTree := NewLiChao(xs)
	for i := 1; i <= n; i++ {
		if i > 1 {
			best := leftTree.Query(a[i])
			delta := pref[i-1] - int64(i)*a[i] + best
			if delta > bestDelta {
				bestDelta = delta
			}
		}
		leftTree.Add(Line{int64(i), -pref[i-1]})
	}

	rightTree := NewLiChao(xs)
	for i := n; i >= 1; i-- {
		if i < n {
			best := rightTree.Query(a[i])
			delta := pref[i] - int64(i)*a[i] + best
			if delta > bestDelta {
				bestDelta = delta
			}
		}
		rightTree.Add(Line{int64(i), -pref[i]})
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	out.WriteString(strconv.FormatInt(initial+bestDelta, 10))
	out.Flush()
}