20

// Algo : Sliding Range Minimum Query

int arr[mx];
int N, D;

void SRMQ() {
    deque <int> dqMin, dqMax;
    for (int i=0; i<N; i++) {
        int num = arr[i];
        while (!dqMin.empty() and dqMin.front()>num)
            dqMin.pop_front();
        dqMin.push_front(num);
        if (i>=D and arr[i-D]==dqMin.back())
            dqMin.pop_back();

		while (!dqMax.empty() and dqMax.front()<num)
            dqMax.pop_front();
        dqMax.push_front(num);
        if (i>=D and arr[i-D]==dqMax.back())
            dqMax.pop_back();

        if (i>=D-1) {
            int mini = dqMin.back();
            int maxi = dqMax.back();
			cout << mini << " " << maxi << endl;
        }
    }
}

// Algo : Sparse Table
//        Find Minimum Number in a given range
// Complexity : computeST -> O(Nlog2N), query -> O(1)

int ST[24][mx], A[mx];

void computeST(int n) {
    for (int i=0; i<n; i++)
        ST[0][i] = i;
    for (int k=1; (1 << k) < n; k++) {
        for (int i=0; i+(1 << k) <= n; i++) {
            int x = ST[k-1][i];
            int y = ST[k-1][i+(1 << (k-1))];
            ST[k][i] = A[x] <= A[y] ? x : y;
        }
    }
}

int RMQ(int i, int j) {
    int k = log2(j-i);
    int x = ST[k][i];
    int y = ST[k][j-(1<<k)+1];
    return A[x] <= A[y] ? x : y;  // return index
}