Untitled

#include<bits/stdc++.h>
using namespace  std;
typedef int  ll;
#define int ll
ll n1;

ll mrg (ll x ,ll y )
{
    return min(x,y);
}
int xy;
struct segment_tree
{
    vector<ll> tree;
    void clear()
    {
        tree.clear();
    }

    void init(int num, const vector<ll>& a)
    {
        n1 = num;
        tree.assign(4*n1,1e9);
        build(a);
    }
    void build(const vector<ll>& a, int id=0,int ns = 0, int ne = n1-1)
    {
        if(ns==ne){
            tree[id] = a[ns];
            return ;
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        build(a,l, ns, md);
        build(a,r, md+1, ne);
        tree[id] = mrg(tree[l],tree[r]);
    }


    ll query(int qs, int qe, int id=0, int ns=0, int ne=n1-1)
    {
        if(ns>qe || qs>ne){
            return 1e9; ///infnity
        }
        if(qs<=ns && qe>=ne){
            return tree[id];
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        ll ndl = query(qs, qe, l, ns, md);
        ll ndr = query(qs, qe,r, md+1,ne);
        return mrg(ndl,ndr );
    }

    void upd(int pos , int val , int id=0, int ns=0,int ne=n1-1)
    {
        if(ns>pos || pos>ne){
            return;
        }
        if(ns==ne){
            tree[id]=val;
            return ;
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        upd(pos, val,l, ns, md);
        upd(pos, val, r, md+1, ne);
        tree[id] = mrg(tree[l],tree[r]);
    }
    int quer(int &l,int &r,int &xx,int id=0,int ns=0,int ne=1e6)
    {
        if (ns>xx)
            return -1e9;
        if (tree[id]>=l)
            return -1e9;
        if (ns==ne)
        {
            return ns;
        }
        int left=2*id+1,right=left+1;
        int md=(ns+ne)/2;
        if (tree[right]<l && ne<=xx)
        {
            return quer(l,r,xx,right,md+1,ne);
        }
        if (tree[right]>=l)
        {
            return quer(l,r,xx,left,ns,md);
        }
        return max(quer(l,r,xx,left,ns,md), quer(l,r,xx,right,md+1,ne));
    }
} ;
void solve()
{
    int n,q;
    cin>>n>>q;
    vector<int>a(n);
    vector<int>freq(1e6+1,-1e9);
    for (auto &x:a)
    {
        cin>>x;
        freq[x]++;
    }
    vector<vector<pair<pair<int,int>,int>>>v(1e6+1);
    for (int i=0;i<q;++i)
    {
        int l,r,x;
        cin>>l>>r>>x;
        l--;
        r--;
        v[r].push_back({{l,x},i});

    }
    segment_tree st;
    st.init(1e6+1,freq);
    vector<int>ans(q,-1);
    for(int i=0;i<=(int)n-1;++i)
    {
        st.upd(a[i],i);
        for (auto [p,qind]:v[i])
        {
            auto [l,x]=p;
            int an=st.quer(l,i,x);
            if (an<0)an=-1;
            ans[qind]=an;
        }
    }
    for (int i=0;i<q;++i)
        cout<<ans[i]<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
}