/*
#############################################################################################%####################################%###############
#--%###*-=+-####--+::::=##%-:*#=:%#*-*#%-::+########%=::+##:=%#*-=#=-##:::::+%-:###-=####-:::=%##-::::*##=:=#####-::*%::::::+#-+###-::*##%--#%%--#
#::%###*:-*:-##=:#=..::-###=.*#-.*#=:**:.:..:#####*#:.:::##.-##+.+#=:##...::+%:.=#%:-####:.::.:%#..:::*#%::.####-.::-%:....:+*:=#*..:.:=##:.=##:-#
#::####*:-%::%#-:%=.#######*.+#:.:%:.%-:*##+:+#####-:#%##*#.-##+:=#=:*#.:%###%::.*%:-###%::##=:*#.-#####+:#.+##::####*##-:%##*.=#-:##%-:#%::.##::#
#::####*:-#+:*#:=#=.::-*####:=*.=:#:-#::%##*.=#####::######.::::.=#=:##..:--#%::--#:-####:.##::##.::-=##-:#:=#+:=#######-:%##*.=%:-###+.=%::-:#::#
#::####+:-#*:+*.*#=:::-#####:-=:+.*.+%::##%*.=*--=#::#####*..::..=#=:*#..::-#%:.+.+:-####:..:.+##:::-=##:=#-:*+:=#######::###*.=#:-###+:-#::*.*.-#
#::%###+:-##:-::%#=:########:::-#:-:%#::*##*.+#--=#::*###*#:-##+:=#=:*#::%###%::%=.:-####:.#::*##:-####*.....#*:-#######-:###*:=%-:###=:+%::#-.::%
#::*****:-##-..+##=.+***####=..##..:##*::%+.:####*#+::#*:##.-##*:=#=:##.:*#**%::#*:.-###%:.##:-##.:***#::###.-%-:-#+-%##-:###*:=#+..#+.-%#::#%:.:#
#:..::+*:=##%::*##=:...:%##%#::##=:-###*:..:#########:::-#*:-##*:+%=:##:..::=%::##+:-###%-:#%=:=%:....+:-###--*#=:.:=###-:###*:+*#*.::-###:-##+:-#
################################################################################################################################################%#
####################################################%#################################################################%#########%#################
%#%#%@%@@%%%%%*%@%#%%%%@@%@@@@@@#%%#***+++@@@@@@@@@@*@@%@@@@@@%#--@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:*@@@@@@@%@@@@@@@@
##%%%@#@@@%%%%###@%%#%@@@@%#@@@@+%%++*%=##%@@@@@@@@@@-#@@@%@@@%#=:@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:*@@@@@@%%=@@@@@@@
-#@@@@%%%%#%%%@%#####%##%#%*##+*+#@#*%%%+%%###@@@@@@@@+.-%@@@@%#-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:+@@@@@@=:@@@@@@@@
--#@@#*%@@@@@@%%@%%#%%%***%@%##*++#+%%%%*=**#%@@@@@@@@@%+:.:-=*#%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:@@@@-.:@@@@@@@@@
:-:*%@@%%%@@%@%%%@#%*%*#%###%%%##*%#**=*+=-+=#=**@@%%*++#@@*=::.:.:::.:-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@%%=-::-%@@@%@@@@@@
+--:*@@@@@@@@@@@@@@@@@%#%#%#%%%%%%#**+++=+**%#=-%%#*+++=%@**%@@@%%+-....::=@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::.-#@@@@@@@@@@@@@
%+:::+@@@@@@@@@@@@@@@%@%#*#%@%*+*%@%@#*+*%%#%%@%%#++*+=#@%*@%@#-=#++*%%-...:#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@+:::::*%#-@@@@@@@@@@@@@@
#%##%%%@@@@@@@@@@@@@@@%@@@@@@%#%%@@%%@#+%%@*+##%%%#*@+*@%@@@@%#::=+++++*%:.::#@@@@@@@@@@@@%=#@@@@@@@@@@@@@@+@#@@@@@@@@@@%+::.+@*#%-:@@@@%@@@@@@@@@
%%%###%%%%###%%%@@@@@@@@%%@%%%#@%%@@@@%%@#%%=*#=++*%%%*@+#@%%@#-::%*%#*=+%=:..%@@@@@@@@@@@%==-=#@%@@@@@@%===*@@@@@@@@@%@#::-%#*+%%:+@@@@@@@@@@@@@@
%#%%##%#%@%#%%%%#%@@@@@%%%@@%%%%@%@%@@@@%@%#*=*=*##*#%%+*@@#*#%#::-#===:-+@:.:*@@@@@@@@@@@%+---==*@@%@@*==--=@@@@@@@@@@%*::%+-:*@+:%@@@@@@@@@@@@@@
%%#%%%###%%%#%###%@#=+=%@@%%@@%@%%@@@@%%%%@@@%@@%#+%###*%%@%@#%#+:.=@#%#**@::.*@@@@@@@@@@@%#=-=-===*@%*-=====#@@@@@@@@@#=:*###%@#:-@@@@@@@@@@@@@@@
%#@#%%%%%%%%%##%#%#@*+++%%@@@@@@#*@@@@@%@@@@@#%@@@**@%*%%@@@@#%@#+:::%*+++@=:.#@@@@@@@@@@@@#*==---=-*#*-==-=-=@@@@@@@@%#::@+*%%-.-@%@@@@@@@@@@@@@@
%##%%%%%%#%%#%%#%#%#@*+++@@%@@@@@@@@@@@@@@@@@@@@%%#%@%@%@@@%*#%#@%*:::=@+*@+::@@@@@@@@@@@%%@%#+==-===@*===-=*@@@%@@@@@#*:+%#+:.:#@%@@@@@@@@@@@@@@@
%##%%%%%###%#%%#%#%#%%*+*+%@@@@@@@@@@@@@@@@@@@@@@@%#@@@@@@@%@%%%#%@%+:.:-#@*::@@@@@@@%%%%%%%%@%#*=--=@*--=##*#@@@@@@@##=:*:-=#%#@@@@@@@@@@@@@@@@@@
##%%#%%%%@%%@%%@%%@@%%@*+*=%@@@@@@%@@@@@@@@@@@@@@@%@@@@@@@@@%@###@%%@%*::-@#=.%@@@@%%##%%%###%%%@%*+=@==#*+*%*++#@@@%#+.=@@*##+++%%@@@@%%%%%%%%%%%
#%#%%%@#%%%%#%%@###%#%%%++*+#@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@%%%%@**@@@%*%%#:+@@%%#%#*++##%#+++++*%%%*++++++*@%@@@##=.-%@%%#%++++@@@@%%%%%%%%%%%%
%@%#%#@%%@%%%%%%%%%%#%%@%%%#=*@@@@@@@@@@@@@@@%@@@@%@@@@@@@@@@@%#%%%#@@@%@%@@##:-%%#*+*#%%%*+++++++++++*++++++++%%##=:.*@@@#%%#++++@@@%%%######%%%%
#%%%%@%%%%#%%%@@@@@%%%%%%%%%@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#%@@%@@%#%%#%%*%@##*-:=+*%%%#*++++++++++++*+++++++++#+:+#@@@@@@@@%*+++@@@%%%##########
%%%%@@@@%%%%%#%#%##%%%%%%#%%%#+==***%@@@@@@@@@@@@@@@@@@@@@@@@@@@@***##*#%%%%%%@%%%#*#@%*+++++++++++++++%++++++++=#*++%@@%@@@@%*+++@@%%%%##########
@@@%%%#%%###%%%%%#######%%%%%##+==#=====*+#%@@@@@@@@@@@@@@%@@@@+*#*+=#%@%#%%%%%%#%%%%%*+++++++**+++++++**+++**++++@+++%%@@@@@@#+=%%%%%%%##########
####%%%%%#%%%%%#%@%#####%%%%%%%*=+=#=====#+==*@@@@@@@@@@@**@@@###%@%%@@#%%%%%%%%##%%@*++++++*%++++++++++*++++###*+#*++*@@@@@%%%*@%%%%%%###########
%##%%%%%%##%%%%##%%######%%#%%%#++=+%=====#===+%@@%%@@@@@%#@@@%%%%%@@%#%%%%%%%%%%%%%%++=++#%#*++++++++++*+++++#==##++++@%@@%%%%####%%##%%######*##
%####%@%#%#%%%%###@%####%###%%%%#====*=====#==++#@@@@@@@@@@@@@@#%%%@%#%%%%%%%%%####%%#%%*===*#++++++++++*+++++#===+%+++%%%%%%%%%%#####%%%%%%%%%%%%
%####%#%#%#%%%%###%@######%%%%%%%+===#+====+%+=+*%@@@@@@@@%%#*%%@@@%%%%#%#%%%%%#++*#%=---==-=+%*++++++++++++++#=====%++*%%%%%%%%%#%###%%%%%%%%%%%@
%######%%%%%%%#%##%%%%%####%%%%%%#++==#======#=++*%@@@@@@@@@@%%@@@%%##%#%%%%##*++++#*-===---=-==##++++++++++**==-===%++#%%%%%%%%%%%%%#%%%%%%%@@@@@
%####%%#%%%%###%%%#%%%#%###%@%%%%%++=++#=====**=+++%@@@@@@@@@@@@@##%#%%%%%%#%*+++++%+==-===--===-=*%*+++++#*==-=--==%++#%%%%%%%%%%%%%%%#*%@@@@@@@@
%#######%@%%@@@%%#%%%%#%%#%%%%%%%##+*==**==+==*==+*+@@@@@@@@@@@@%%%%#%%%%%%#+++++++%+=========--====+%%**-=--====-==%++#@@%@%%%%#*%%%%%#%**+*@%@@%
%%#%%#%%#%@#****#%@@@@@%%@@@@@@@@@@@@@@@@%%#***+*++++%@@@@@@@@@%%%%%%%#%%%%*+++++++%+===-==========--====---=====-=+%++#@@@%%+++###%#%-=+#=-#%@@@#
%%##%%%#%##@##*******##%%%%%%#####**#**#*****##%@@%%%#@@@@@@@@%%%%%%%%%#%#*++++++++##=-====---=---==--==--=======-=*#++@@%#=*+++--:-=-+-==#*=++*=-
#%##%%%####%@%#%%%%%%%%%%%#***********************#%@@@@@@@@@@%%%%%%##%##*++++++++++%=---=--===--===========-==-==-%#+*@#**%#%%%@#*%%%%%#%@@%-*==*
%@#********##%%%%%%%%%%%##****************************%@@@@@@%#%%%%%#%%%*+++++++++++*%*-=-=-=-+%=-===========-*#==-%*=%+==%%%%%@@@##@%%@@@@@%@%%%%
%%%%%%%%%%%%%%%%%%%%%%%#********************************#%@@@%##%#%%#%%*+++++++++++*++#%==--=%*%============--%%=-*#+%%%%%%%@@@@%@%@@@@@@@@@%@@@%@
%%%%%%%%%%%%%%%%%%%%%%%#*******************************##%%%%#%%%%%%%%*++++++++=+#@#+++%%=-+#+*%====-=----===-##*#++++%%%%%@%%%@@@@@@@@@@@@@@@@@@@
%%%%%%%%%%%#@%%%%%%%%%%###****************************#%%%#%#%%%%%%%%#++++++++#@%###++**###++++##-====--=====#**%*++++*@@@%##%@@@@@@@@@@@@@@@@@@@@
%%%%@%*++++++%%%%%%%%%%%%%####*************####%%#%#**#%###%%%#%%%%%#+++*#%@%#*+++#%+%++++++++++#%==-===--=+%+++++++#==#%%%%@@@@@@@@@@@@@@@@@@@@@@
%%@#+=+++++++*%@@@%%*+++*@%%%%%%%%%##%%%@@%%%#++==**+%#########%%@%%%#%%%%#%*+++++***=+++++++++++*%#===-==@*++++++++*%++%%@@@@@@@@@@@@@@@@@@@@@@@@
@#+=+++++++++++++++=++++++%%%%%%%%%%%%%%###%#%*====##%##########%%%%%#%###%#+++=*++++++++++++++++++#@*-+%*+=+++++++++@++#@@@@@@@@@@@@@@@@@@@@@@@@@
#+++++++++++++++++++++++++%%%%%@@@%##%%@#%%%%##+=*%##########%#@%%%%%%%%%%%++++#++++++++++++++++++++++#++++++++++++++*#++@@@@@@@@@@@@@@@@@@@@@@@@@
#+++++*++++%++++++++++++++#@%@%%%#%##%%%%%%#%#%#%##############@%%%%%%%%%#++++*=++=+++++++++++++++++++*+++++++++++++++%++%@@@@@@@@@@@@@@@%%@%@@@@@
##%%%#++++#=++++++#+++++++*%#%%@%#######%#%%#%%%###%##########%#%%%%%@%#%*+++**=+++++++++++++++++++=++#+++++++++++++++%++#@%@@@@@@@@@@@@@@@@@%@%%#
%%%%%++++%+++++++*@%#+=+++*%%%#%@#%%###%%@%#%%##############%%%%%%#%@%#%*++++*++++++++++++++++++++++++#+++++++++++++++#*+#@@@@@@@@@@%%#########%%%
%%%@%*++*++++++++#@%@%####@%%%#%%@#%####%#%%%#%##############%%%%%%%@%%%++++*+++++++++++++++++++++++++#++++++++=++++++#%%@###*###%%%%%@@@@@@@@@@@@
%%%@##++*+++++++*%@%%@@%%%@%%##%%%%##%%%#%%%%################%%#%%#@%%%#+++++=++++++++++++++++++++++++#+++++++*+++++++#%%%@%%%%#%%@%#%@@@@@@@@@@@@
%%%@%##+*++++++#%@%%##@%%%%##%%%#%@%#%#%#%%#################%@%%#+=*##%%*++++++++++++++=+++++++++++=+=#+++++++*+++++++#@%%%%##%@@@@@@@@@@@@@@@@@@@
%%%%@%##**++##%%%##%##%@%%#%#%%##%#@%#%%%#############%######+--====%%#%#+++++++++++++*+++++++++++++++#++++++**+++++++##***#%#%@@@@@@@@@@@@@@@@@@@
%%%%%@%#%##%##%%##%#%%%%%#%%#%%%%%##@%#@%########%###%@#####==-======@%%#+++++++++++++#=++++++++++++#=*%+++++#++++++++%#*#%@@@%@@@@@%@@%%@@%%@@@@@
%%%%%%@%#%%%%@%##%%#%%%%%@%##%%%%%%%%%%%###########@%#%####=--=-=-=*%#@#%*++++++++++++@*++++++++++*+==-=##+++@*+++++++%%@%%@@@@@@@%%@%%%%%%@@@@@@@
%%%%%%%@%#%@%#%%%#%%##%%##@%#%%%%%#%#%%#%###%###%@###%%###=======+@*+=#@%%+++++++++++%*%+++++++=*#-=--====@+*+%+++++++%@@@@%%%%%%%%%%@@%@@@@@@@@@@
%%%%@%%#%%%%@%%%%%%%######%%%##%%#%%#@%######@@######%%%#=-=--=%%#+-===*@%#++++++++%+==#*++++=*%=-======-====-+%*+++++@%%%@@@%%%%%@%%@@@@@@@@@@@@@
@@#####%###%#%#%%%%%####%##%@%#%%%@%#%%%%%%##########%%*=-==#@#%==-=-==-+%@+++++##===-==@+++#*==-=======-==--===%#+++##@@@@%%%%%%%%%@@@@@@@@@@@@@@
%###%%%%##%%%#@%%%%%%%%##%#%%@%@%#%##%###############%#%%##%#*---=-==--===*%###==-====-=+%%=----=-=====--===-==-=%%++@=%@%%%%%%%%%@@@@@%@@@@@@@@@@
%%%############@#%#%%%%#%#%#%@%#%###########################==-======--======-===--===--===--==========-----======#%%-=+%%%@@%%%@@@@@@@@@@@@@@@@@@
%%%%%#########%#%#%%%%%%%#@@###############################*=====-------=--==--==---==-=====-============-=-=======---==%@@%%%%%%@@@@@@@@@@@@@@@@@
%%%%%##########%#@#%%#%%@%##%##########################%###==-=====------======-=-=----=-#=====-===-=--=====--=--======-@@@@@@@@@@@@@@@@@@@@@@@@@@
%%%%%#########%%##%%%#%%##################################*========------=======+===---=#%==---=-==@==-===-*==-=-======-%@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%#########%##%%%#@################################%###=-==========---=-====*%===-==*%%==-==-==@#%-=--==%+-===-====--#@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%%%########%#%#@%################%##################%*=====-===-===--=-==-#%%--=-=*##%+-=====@*#%@---==%%-==--=====-*@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%%%%########%#@###################################%##=-======-%====--=-==%#%+=-=-@#*%%*-=--+%*++##%*-==%%%---=----=-*@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%%%%########%###############%@%%##%#################*-========@%+==-==-*@+%@=-=%%*++%%#==*%#++=++%%%%*@#%%#--======-*@@@@@@@@@@@@@@@@@@@@@@@@@
#%%%%%%%######%%%############%@%#%#@####################=-=======+##@*-==@@**=%%###*+=++##%%%#*+++++++*#%%*+###@+=====-=%@@@@@@@@@@@@@@@@@@@@@@@@@
*/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;

struct Seg {
    int n;
    vector<int> seg;
    vector<int> lazy;
    Seg() {}
    Seg(int n) {
        this->n = n;
        seg.resize(4 * n, INF);
        lazy.resize(4 * n);
    }
    void prop(int p) {
        if(lazy[p]) {
            seg[p * 2] += lazy[p];
            lazy[p * 2] += lazy[p];
            seg[p * 2 + 1] += lazy[p];
            lazy[p * 2 + 1] += lazy[p];
            lazy[p] = 0;
        }
    }
    void update(int p, int l, int r, int i, int j, int x) {
        if(l == i && r == j) {
            seg[p] += x;
            lazy[p] += x;
            return;
        }
        prop(p);
        int mid = l + (r - l) / 2;
        if(i <= mid) {
            update(p * 2, l, mid, i, min(j, mid), x);
        }
        if(j > mid) {
            update(p * 2 + 1, mid + 1, r, max(i, mid + 1), j, x);
        }
        seg[p] = min(seg[p * 2], seg[p * 2 + 1]);
    }
    void update2(int p, int l, int r, int i, int x) {
        if(l == r) {
            seg[p] = x;
            return;
        }
        prop(p);
        int mid = l + (r - l) / 2;
        if(i <= mid) {
            update2(p * 2, l, mid, i, x);
        } else {
            update2(p * 2 + 1, mid + 1, r, i, x);
        }
        seg[p] = min(seg[p * 2], seg[p * 2 + 1]);
    }
    int query(int p, int l, int r, int i, int j) {
        if(l == i && r == j) {
            return seg[p];
        }
        prop(p);
        int mid = l + (r - l) / 2;
        int wochien = INF;
        if(i <= mid) {
            wochien = query(p * 2, l, mid, i, min(j, mid));
        }
        if(j > mid) {
            wochien = min(wochien, query(p * 2 + 1, mid + 1, r, max(i, mid + 1), j));
        }
        return wochien;
    }
};

int n; int q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> wochien(q);
    vector<vector<array<int, 2>>> right(n);
    for(int i = 0; i < q; i++) {
        int l; int r;
        cin >> l >> r;
        l--; r--;
        right[l].push_back({r, i});
    }
    stack<int> stk;
    Seg seg(n);
    map<int, int> mp;
    int nearestDuplicate = n;
    for(int i = n - 1; i >= 0; i--) {
        while(stk.size() && a[i] > a[stk.top()]) {
            int cur = stk.top(); stk.pop();
            int r = (stk.size() ? stk.top() - 1 : n - 1);
            seg.update(1, 0, n - 1, cur, r, a[i] - a[cur]);
        }
        nearestDuplicate = min(nearestDuplicate, (mp.count(a[i]) ? mp[a[i]] : n));
        mp[a[i]] = i;
        if(i + 1 < n) {
            seg.update(1, 0, n - 1, i + 1, n - 1, -1);
        }
        seg.update2(1, 0, n - 1, i, a[i] - 1);
        stk.push(i);
        for(array<int, 2> j : right[i]) {
            wochien[j[1]] = seg.query(1, 0, n - 1, i, min(nearestDuplicate - 1, j[0]));
        }
    }
    for(int i : wochien) {
        cout << i << "\n";
    }
}