Shared code

#include <bits/stdc++.h>
using namespace std;
#define si short int
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007
#define endl "\n"
#define space " "
#define all(argument) argument.begin(), argument.end()
#define dbg(argument) cout << __LINE__ << ".. " << argument << endl;
template <typename typC, typename typD>
istream &operator>>(istream &cin, pair<typC, typD> &a) { return cin >> a.first >> a.second; }
template <typename typC>
istream &operator>>(istream &cin, vector<typC> &a)
{
    for (auto &x : a)
        cin >> x;
    return cin;
}
template <typename typC, typename typD>
ostream &operator<<(ostream &cout, const pair<typC, typD> &a) { return cout << '{' << a.first << ',' << a.second << '}'; }
template <typename typC, typename typD>
ostream &operator<<(ostream &cout, const vector<pair<typC, typD>> &a)
{
    for (auto &x : a)
        cout << x << '\n';
    return cout;
}
template <typename typC>
ostream &operator<<(ostream &cout, const vector<typC> &a)
{
    int n = a.size();
    if (!n)
        return cout;
    cout << a[0];
    for (int i = 1; i < n; i++)
        cout << ' ' << a[i];
    return cout;
}
///////////////////////// Garvit_Goyal /////////////////////////////
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    /* #ifndef ONLINE_JUDGE
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     #endif*/
 
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    cin >> a;
    a.push_back(1e9), n++;
    vector<int> par(n, n-1);
    stack<int> st;
    for (int i = 0; i < n; i++)
    {
        while (!st.empty())
        {
            int tp = st.top();
            if (a[tp] < a[i])
            {
                st.pop();
                par[tp] = i;
            }
            else
            {
                break;
            }
        }
        st.push(i);
    }
    vector<vector<int>> bl(n, vector<int>(18, n-1)); // binary lifting
    for (int p = 0; p < 18; p++)
    {
        for (int i = 0; i < n; i++)
        {
            if (p == 0)
            {
                bl[i][p] = par[i];
            }
            else
            {
                bl[i][p] = bl[bl[i][p - 1]][p - 1];
            }
        }
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        l--, r--;
        int anstemp = 1;
        for (int i = 17; i >= 0; --i) {
			if (bl[l][i] <= r) {
				l = bl[l][i];
				anstemp += (1<<i);
			}
		}
        cout << anstemp << endl;
    }
 
    return 0;
}