#include <bits/stdc++.h>

using namespace std;

int main() {
    ifstream cin("rmq.in");
    ofstream cout("rmq.out");
    int n, m;
    cin >> n >> m;
    
    vector < vector <int> > rmq(20);
    rmq[0].resize(n);
    for (int i = 0; i < n; ++i) 
        cin >> rmq[0][i];

    for (int i = 1; (1 << i) < n; ++i) {
        rmq[i].resize(n);
        for (int j = 0; j + (1 << (i - 1)) < n; ++j) 
            rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))] - rmq[i][j]);
    }
    
    while (m--) {
        int x, y; cin >> x >> y; --x; --y;

        int len = log2(y - x + 1);

        cout << min(rmq[len][x], rmq[len][y - (1 << len) + 1]) << '\n';
    }

    return 0;
}