#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define loop(i, a) for (int i = 0; i < (a); ++i)
#define cont(i, a) for (int i = 1; i <= (a); ++i)
#define circ(i, a, b) for (int i = (a); i <= (b); ++i)
#define range(i, a, b, c) for (int i = (a); (c) > 0 ? i <= (b) : i >= (b); i += (c))
#define parse(it, x) for (auto &it : (x))
#define pub push_back
#define pob pop_back
#define emb emplace_back
#define mak make_pair
#define mkt make_tuple
typedef long long ll;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int maxn = 25005, maxq = 100005, blk = 233;
int n, q;
int a[maxn], pos[maxn];
vector<pair<int, int> > qs[maxn];
vector<pair<int, int*> > es[maxn];
int ls[maxq], rs[maxq], ord[maxq];
vector<int> gl[maxn], gr[maxn], bl[maxn], el[maxn], br[maxn], er[maxn];

struct Fenwick {
    int dt[maxn];
    void inline init() {
        cont(i, n) dt[i] = q + 1;
    }
    void inline add(int a, int x) {
        while (a <= n) {
            dt[a] = min(dt[a], x);
            a += a & -a;
        }
    }
    int inline get(int a) {
        int res = q + 1;
        while (a) {
            res = min(res, dt[a]);
            a -= a & -a;
        }
        return res;
    }
} bit;

set<int> st;
set<pair<int, int> > nb;

namespace MoQ {
    void inline Add(int x) {
        auto it = st.insert(x).first;
        if (it != st.begin()) nb.emplace(*prev(it), x);
        if (next(it) != st.end()) nb.emplace(x, *next(it));
        if (it != st.begin() && next(it) != st.end()) nb.erase(mak(*prev(it), *next(it)));
    }

    void inline Del(int x) {
        auto it = st.find(x);
        if (it != st.begin()) nb.erase(mak(*prev(it), x));
        if (next(it) != st.end()) nb.erase(mak(x, *next(it)));
        if (it != st.begin() && next(it) != st.end()) nb.emplace(*prev(it), *next(it));
        st.erase(it);
    }

    int nl = 1, nr = 0;

    void inline Access(int l, int r) {
        while (nl > l) Add(a[--nl]);
        while (nr < r) Add(a[++nr]);
        while (nl < l) Del(a[nl++]);
        while (nr > r) Del(a[nr--]);
    }
}
using MoQ::Access;

int res[maxq];

int main() {
    scanf("%d%d", &n, &q);
    cont(i, n) {
        scanf("%d", a + i);
        pos[a[i]] = i;
    }
    cont(i, q) {
        scanf("%d%d", ls + i, rs + i);
        qs[rs[i]].emb(ls[i], i);
        ord[i] = i;
    }
    sort(ord + 1, ord + q + 1, [&] (int a, int b) {
        return mak(ls[a] / blk, rs[a]) < mak(ls[b] / blk, rs[b]);
    });
    cont($i, q) {
        int i = ord[$i];
        Access(ls[i], rs[i]);
        parse(it, nb) {
            int lp = pos[it.first], rp = pos[it.second];
            if (lp < rp) gr[lp].pub(rp);
            else gl[lp].pub(rp);
        }
        nb.clear();
    }
    cont(i, n) {
        sort(all(gl[i]), greater<int>());
        gl[i].erase(unique(all(gl[i])), gl[i].end());
        sort(all(gr[i]));
        gr[i].erase(unique(all(gr[i])), gr[i].end());
        bl[i].resize(SZ(gl[i])); el[i].resize(SZ(gl[i]));
        br[i].resize(SZ(gr[i])); er[i].resize(SZ(gr[i]));
        int p = 0;
        loop(j, SZ(gl[i])) {
            while (p < SZ(gr[i]) && a[gr[i][p]] > a[gl[i][j]]) ++p;
            es[i].emb(gl[i][j], &bl[i][j]);
            if (p < SZ(gr[i])) {
                es[gr[i][p]].emb(gl[i][j], &el[i][j]);
            } else {
                el[i][j] = q + 1;
            }
        }
        p = 0;
        loop(j, SZ(gr[i])) {
            while (p < SZ(gl[i]) && a[gl[i][p]] > a[gr[i][j]]) ++p;
            es[gr[i][j]].emb(i, &br[i][j]);
            if (p < SZ(gl[i])) {
                es[gr[i][j]].emb(gl[i][p], &er[i][j]);
            } else {
                er[i][j] = q + 1;
            }
        }
    }
    bit.init();
    range(i, n, 1, -1) {
        parse(it, qs[i]) bit.add(it.first, it.second);
        parse(it, es[i]) *it.second = bit.get(it.first);
    }
    cont(i, n) {
        loop(j, SZ(gl[i])) {
            int tl = bl[i][j], tr = min(j < SZ(gl[i]) - 1 ? bl[i][j + 1] : q + 1, el[i][j]);
            if (tl < tr) ++res[tl], --res[tr];
        }
        loop(j, SZ(gr[i])) {
            int tl = br[i][j], tr = min(j < SZ(gr[i]) - 1 ? br[i][j + 1] : q + 1, er[i][j]);
            if (tl < tr) ++res[tl], --res[tr];
        }
    }
    partial_sum(res, res + q + 1, res);
    cont(i, q) printf("%d\n", res[i]);
    return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

Touko's favorite sequence of numbers is a permutation a_1, a_2, ..., a_n of 1, 2, ..., n, and she wants some collection of permutations that are similar to her favorite permutation.

She has a collection of q intervals of the form [l_i, r_i] with 1 ≤ l_i ≤ r_i ≤ n. To create permutations that are similar to her favorite permutation, she coined the following definition:

  * A permutation b_1, b_2, ..., b_n allows an interval [l', r'] to holds its shape if for any pair of integers (x, y) such that l' ≤ x < y ≤ r', we have b_x < b_y if and only if a_x < a_y. 
  * A permutation b_1, b_2, ..., b_n is k-similar if b allows all intervals [l_i, r_i] for all 1 ≤ i ≤ k to hold their shapes. 



Yuu wants to figure out all k-similar permutations for Touko, but it turns out this is a very hard task; instead, Yuu will encode the set of all k-similar permutations with directed acylic graphs (DAG). Yuu also coined the following definitions for herself:

  * A permutation b_1, b_2, ..., b_n satisfies a DAG G' if for all edge u → v in G', we must have b_u < b_v. 
  * A k-encoding is a DAG G_k on the set of vertices 1, 2, ..., n such that a permutation b_1, b_2, ..., b_n satisfies G_k if and only if b is k-similar. 



Since Yuu is free today, she wants to figure out the minimum number of edges among all k-encodings for each k from 1 to q.

Input

The first line contains two integers n and q (1 ≤ n ≤ 25 000, 1 ≤ q ≤ 100 000).

The second line contains n integers a_1, a_2, ..., a_n which form a permutation of 1, 2, ..., n.

The i-th of the following q lines contains two integers l_i and r_i. (1 ≤ l_i ≤ r_i ≤ n).

Output

Print q lines. The k-th of them should contain a single integer — The minimum number of edges among all k-encodings.

Examples

Input


4 3
2 4 1 3
1 3
2 4
1 4


Output


2
4
3


Input


8 4
3 7 4 8 1 5 2 6
3 6
1 6
3 8
1 8


Output


3
5
9
7


Input


10 10
10 5 1 2 7 3 9 4 6 8
2 2
4 5
6 8
4 10
4 4
2 7
2 2
7 8
3 7
2 10


Output


0
1
3
6
6
9
9
9
9
8

Note

For the first test case:

  * All 1-similar permutations must allow the interval [1, 3] to hold its shape. Therefore, the set of all 1-similar permutations is \{[3, 4, 2, 1], [3, 4, 1, 2], [2, 4, 1, 3], [2, 3, 1, 4]\}. The optimal encoding of these permutations is <image>
  * All 2-similar permutations must allow the intervals [1, 3] and [2, 4] to hold their shapes. Therefore, the set of all 2-similar permutations is \{[3, 4, 1, 2], [2, 4, 1, 3]\}. The optimal encoding of these permutations is <image>
  * All 3-similar permutations must allow the intervals [1, 3], [2, 4], and [1, 4] to hold their shapes. Therefore, the set of all 3-similar permutations only includes [2, 4, 1, 3]. The optimal encoding of this permutation is <image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define loop(i, a) for (int i = 0; i < (a); ++i)
#define cont(i, a) for (int i = 1; i <= (a); ++i)
#define circ(i, a, b) for (int i = (a); i <= (b); ++i)
#define range(i, a, b, c) for (int i = (a); (c) > 0 ? i <= (b) : i >= (b); i += (c))
#define parse(it, x) for (auto &it : (x))
#define pub push_back
#define pob pop_back
#define emb emplace_back
#define mak make_pair
#define mkt make_tuple
typedef long long ll;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int maxn = 25005, maxq = 100005, blk = 233;
int n, q;
int a[maxn], pos[maxn];
vector<pair<int, int> > qs[maxn];
vector<pair<int, int*> > es[maxn];
int ls[maxq], rs[maxq], ord[maxq];
vector<int> gl[maxn], gr[maxn], bl[maxn], el[maxn], br[maxn], er[maxn];

struct Fenwick {
    int dt[maxn];
    void inline init() {
        cont(i, n) dt[i] = q + 1;
    }
    void inline add(int a, int x) {
        while (a <= n) {
            dt[a] = min(dt[a], x);
            a += a & -a;
        }
    }
    int inline get(int a) {
        int res = q + 1;
        while (a) {
            res = min(res, dt[a]);
            a -= a & -a;
        }
        return res;
    }
} bit;

set<int> st;
set<pair<int, int> > nb;

namespace MoQ {
    void inline Add(int x) {
        auto it = st.insert(x).first;
        if (it != st.begin()) nb.emplace(*prev(it), x);
        if (next(it) != st.end()) nb.emplace(x, *next(it));
        if (it != st.begin() && next(it) != st.end()) nb.erase(mak(*prev(it), *next(it)));
    }

    void inline Del(int x) {
        auto it = st.find(x);
        if (it != st.begin()) nb.erase(mak(*prev(it), x));
        if (next(it) != st.end()) nb.erase(mak(x, *next(it)));
        if (it != st.begin() && next(it) != st.end()) nb.emplace(*prev(it), *next(it));
        st.erase(it);
    }

    int nl = 1, nr = 0;

    void inline Access(int l, int r) {
        while (nl > l) Add(a[--nl]);
        while (nr < r) Add(a[++nr]);
        while (nl < l) Del(a[nl++]);
        while (nr > r) Del(a[nr--]);
    }
}
using MoQ::Access;

int res[maxq];

int main() {
    scanf("%d%d", &n, &q);
    cont(i, n) {
        scanf("%d", a + i);
        pos[a[i]] = i;
    }
    cont(i, q) {
        scanf("%d%d", ls + i, rs + i);
        qs[rs[i]].emb(ls[i], i);
        ord[i] = i;
    }
    sort(ord + 1, ord + q + 1, [&] (int a, int b) {
        return mak(ls[a] / blk, rs[a]) < mak(ls[b] / blk, rs[b]);
    });
    cont($i, q) {
        int i = ord[$i];
        Access(ls[i], rs[i]);
        parse(it, nb) {
            int lp = pos[it.first], rp = pos[it.second];
            if (lp < rp) gr[lp].pub(rp);
            else gl[lp].pub(rp);
        }
        nb.clear();
    }
    cont(i, n) {
        sort(all(gl[i]), greater<int>());
        gl[i].erase(unique(all(gl[i])), gl[i].end());
        sort(all(gr[i]));
        gr[i].erase(unique(all(gr[i])), gr[i].end());
        bl[i].resize(SZ(gl[i])); el[i].resize(SZ(gl[i]));
        br[i].resize(SZ(gr[i])); er[i].resize(SZ(gr[i]));
        int p = 0;
        loop(j, SZ(gl[i])) {
            while (p < SZ(gr[i]) && a[gr[i][p]] > a[gl[i][j]]) ++p;
            es[i].emb(gl[i][j], &bl[i][j]);
            if (p < SZ(gr[i])) {
                es[gr[i][p]].emb(gl[i][j], &el[i][j]);
            } else {
                el[i][j] = q + 1;
            }
        }
        p = 0;
        loop(j, SZ(gr[i])) {
            while (p < SZ(gl[i]) && a[gl[i][p]] > a[gr[i][j]]) ++p;
            es[gr[i][j]].emb(i, &br[i][j]);
            if (p < SZ(gl[i])) {
                es[gr[i][j]].emb(gl[i][p], &er[i][j]);
            } else {
                er[i][j] = q + 1;
            }
        }
    }
    bit.init();
    range(i, n, 1, -1) {
        parse(it, qs[i]) bit.add(it.first, it.second);
        parse(it, es[i]) *it.second = bit.get(it.first);
    }
    cont(i, n) {
        loop(j, SZ(gl[i])) {
            int tl = bl[i][j], tr = min(j < SZ(gl[i]) - 1 ? bl[i][j + 1] : q + 1, el[i][j]);
            if (tl < tr) ++res[tl], --res[tr];
        }
        loop(j, SZ(gr[i])) {
            int tl = br[i][j], tr = min(j < SZ(gr[i]) - 1 ? br[i][j + 1] : q + 1, er[i][j]);
            if (tl < tr) ++res[tl], --res[tr];
        }
    }
    partial_sum(res, res + q + 1, res);
    cont(i, q) printf("%d\n", res[i]);
    return 0;
}

```