Envío 5192

Código

# kinda feel like using segment trees

class SegmentTree:
    def __init__(self, arr):
        self.arr = arr
        self.tree = [0 for _ in range(4 * len(arr))]
        self._build_tree(1, 0, len(arr) - 1)

    def _build_tree(self, i, l, r):
        if l == r:
            self.tree[i] = (self.arr[l], l)
            return self.tree[i]
        mid = (l + r) >> 1
        lsq = self._build_tree(2 * i, l, mid)
        rsq = self._build_tree(2 * i + 1, mid + 1, r)
        self.tree[i] = max(lsq, rsq, key = lambda x: (x[0], -x[1]))
        return self.tree[i]

    def query(self, l, r):
        return self._query(1, l, r, 0, len(self.arr) - 1)[1]


    def _query(self, i, l, r, ll, rr):
        if ll == l and rr == r:
            return self.tree[i]
        mid = (ll + rr) >> 1
        if r <= mid:
            return self._query(2 * i, l, r, ll, mid)
        elif l > mid:
            return self._query(2 * i + 1, l, r, mid + 1, rr)
        lsq = self._query(2 * i, l, mid, ll, mid)
        rsq = self._query(2 * i + 1, mid + 1, r, mid + 1, rr)
        return max(lsq, rsq, key = lambda x: (x[0], -x[1]))

    def __repr__(self):
        return f"arr: {self.arr} tree: {self.tree}"

N = int(input())

arr = list(map(int, input().split(" ")))
st = SegmentTree(arr)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split(" "))
    print(st.query(l, r))