package main

import (
    "math/rand"
    "strconv"
    "testing"
)

func makeRandomSlice(rnd *rand.Rand, n int) []int {
    s := make([]int, n)
    for i := 0; i < len(s); i++ {
        s[i] = rnd.Intn(65535)
    }
    return s
}

func BenchmarkFence(b *testing.B) {
    ranges := []int{10, 100, 1000, 10_000, 100_000}

    rnd := rand.New(rand.NewSource(12345))

    var slices [][]int
    for _, r := range ranges {
        slices = append(slices, makeRandomSlice(rnd, r))
    }
    b.ResetTimer()

    for si, r := range ranges {
        b.Run(strconv.Itoa(r), func(b *testing.B) {
            for i := 0; i < b.N; i++ {
                _ = solve(slices[si])
            }
        })
    }
}

func solve(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    if len(arr) == 1 {
        return arr[0]
    }
    mid := len(arr) / 2
    leftMax := solve(arr[:mid])
    rightMax := solve(arr[mid:])
    midMax := findMidMax(arr)

    return max(leftMax, max(rightMax, midMax))
}

func findMidMax(arr []int) int {
    mid := len(arr) / 2
    left, right := mid-1, mid
    minHeight := min(arr[left], arr[right])
    ret := minHeight * 2
    for left > 0 || right+1 < len(arr) {
        if left > 0 && (right+1 == len(arr) || arr[left-1] > arr[right+1]) {
            left--
            minHeight = min(minHeight, arr[left])
        } else {
            right++
            minHeight = min(minHeight, arr[right])
        }
        ret = max(ret, minHeight*(right-left+1))
    }
    return ret
}

func min(a int, b int) int {
    if a > b {
        return b
    }
    return a
}
func max(a int, b int) int {
    if a < b {
        return b
    }
    return a
}