#include #include using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; using mint = atcoder::modint998244353; void solve() { int n, q; cin >> n >> q; vector a(n); rep(i, 0, n) cin >> a[i]; reverse(a.begin(), a.end()); vector l(q), r(q); rep(i, 0, q) cin >> l[i] >> r[i]; rep(i, 0, q) l[i]--; rep(i, 0, q) { l[i] = n - l[i]; r[i] = n - r[i]; } swap(l, r); vector p(q); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&](int i, int j) { if (r[i] == r[j]) return l[i] < l[j]; return r[i] < r[j]; }); int nr = 0; atcoder::fenwick_tree ft(n); set> st; vector ans(q); for (int i : p) { while (nr < r[i]) { while (!st.empty() && st.begin()->first < a[nr]) { ft.add(st.begin()->second, -1); st.erase(st.begin()); } ft.add(nr, 1); st.insert({a[nr], nr}); nr++; } ans[i] = r[i] - l[i] - ft.sum(l[i], r[i]); } rep(i, 0, q) cout << ans[i] << '\n'; } int main() { int t = 1; // cin >> t; while (t--) solve(); }