package main

import "fmt"

type BitTree []int

func main() { // O(nlogn)
    input := []int{-1, 3, -4, 5, 1, -6, 2, 1}
    tr := ConstructorBIT(input) // O(nlogn)
    total := tr.Sum(len(input) - 1)
    for i := 1; i < len(input); i++ {
        n := tr.Sum(i - 1) // O(nlogn)
        if total-n-input[i] == n {
            fmt.Println(i)
            return
        }
    }
    fmt.Println(-1)
}

func ConstructorBIT(input []int) BitTree {
    t := make(BitTree, len(input)+1)
    for i, v := range input {
        t.Update(i, v)
    }
    return t
}

func (t BitTree) Sum(index int) int {
    s := 0
    index++
    for index > 0 {
        s += t[index]
        index -= index & (-index)
    }
    return s
}

func (t BitTree) Update(index, value int) {
    index++
    for index < len(t) {
        t[index] += value
        index += index & (-index)
    }
}