ДЕРЕВО ОТРЕЗКОВ

                1
      2                   3
  4        5         6         7
8   9   10   11   12   13   14   15
1   2   3    4    5    -1   -1   -1


n
a1 a2 a3 ... an
m
l1 r1
l2 r2
.
.
.
ln rn


#include <iostream>

using namespace std;

int main() {

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    sz = 1;

    while(sz < n)
        sz *= 2;

    for (int i = sz; i <= sz + n - 1; i++)
        t[i] = a[i - sz + 1];

    for (int i = sz + n; i <= sz + sz - 1; i++)
        t[i] = -inf;

    for (int i = sz - 1; i >= 1; i--)
        t[i] = max(t[i * 2], t[i * 2 + 1]);

}