int dp[20][maxn];
void () {
    for (int i = 1; i <= n; i++) dp[0][i] = i;
    for (int j = 1; j < 20; j++)
        for (int i = 1; i + (1 << j) <= n + 1; i++) {
            int l = dp[j - 1][i];
            int r = dp[j - 1][i + (1 << (j - 1))];
            if (a[l] > a[r]) dp[j][i] = l;
            else dp[j][i] = r;
        }
}
int qmax(int l, int r) {
    int k = __lg(r - l + 1);
    int x = dp[k][l], y = dp[k][r - (1 << k) + 1];
    if (a[x] > a[y]) return x;
    else return y;
}