RMQ.java

int n = in.readInt();
int q = in.readInt();
int[] a = IOUtils.readIntArray(in, n);

double log2 = Math.log(2);
int logN = (int) (Math.log(n) / log2);
int[][] m = new int[n][logN + 1];
for (int i = 0; i < n; ++i) m[i][0] = i;
for (int j = 1; 1 << j < n; ++j) {
    for (int i = 0; i + (1 << j) - 1 < n; ++i) {
        if (a[m[i][j - 1]] < a[m[i + (1 << (j - 1))][j - 1]])
            m[i][j] = m[i][j - 1];
        else
            m[i][j] = m[i + (1 << (j - 1))][j - 1];
    }
}

while (q-- > 0) {
    int l = in.readInt() - 1;
    int r = in.readInt() - 1;
    int k = (int) (Math.log(r - l + 1) / log2);
    out.println(Math.min(a[m[l][k]], a[m[r - (1 << k) + 1][k]]));
}