HackerEarth Min difference queries problem solution

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int t[1 << 23];
int L[1 << 23];
int R[1 << 23];
int Root[1 << 23];
int SZ = -1;
int get(int &k)
{
    if (k == -1)
        k = ++SZ,L[SZ] = R[SZ] = -1,t[SZ] = 0;
    return k;
}
void build(int l,int r,int node)
{
    if (l == r)
        return ;
    int m = (l + r) / 2;
    build(l,m,get(L[node]));
    build(m+1,r,get(R[node]));
}
void update(int l,int r,int pos,int v,int node,int prev)
{
    if (l == r)
        t[node] = v;
    else
    {
        int m = (l + r) / 2;
        if (pos <= m)
            R[node] = R[prev];
        else
            L[node] = L[prev];
        if (pos <= m)
            update(l,m,pos,v,get(L[node]),L[prev]);
        else
            update(m+1,r,pos,v,get(R[node]),R[prev]);
        t[node] = t[get(L[node])] + t[get(R[node])];
    }
}
int query(int l,int r,int l1,int r1,int node)
{
    if (l1 <= l && r <= r1)
        return t[node];
    int m = (l + r) / 2;
    int ans = 0;
    if (l1 <= m)
        ans += query(l,m,l1,r1,L[node]);
    if (m+1<=r1)
        ans += query(m+1,r,l1,r1,R[node]);
    return ans;
}
vi ss;
void go(int l,int r,int l1,int r1,int node)
{
    if (!t[node])
        return;
    if (l == r)
        return void(ss.pb(l));
    int m = (l + r) / 2;
    if (l1 <= m)
        go(l,m,l1,r1,L[node]);
    if (m+1<=r1)
        go(m+1,r,l1,r1,R[node]);
}
const int N = (int)(1e6) + 5;
vi v[N];
int s[N];
int last[N];
int wh[N];
int n;
int get(int l,int r,int k)
{
    return lower_bound(all(v[k]),r + 1) - lower_bound(all(v[k]),l);
}
int get(int l,int r)
{
    vi w;
    int d = query(1,n,l,r,Root[r]);
    if (d > wh[r - l + 1])
        return 0;
    if (d == 1)
        return -1;
    ss.clear();
    go(1,n,l,r,Root[r]);
    for (auto &it : ss)
        it = s[it];
    for (auto it : ss)
        w.pb(get(l,r,it));
    sort(all(w));
    int ans = 1e9;
    for (int i = 0;i + 1 < d;++i)
        smin(ans,w[i + 1] - w[i]);
    return ans;
}
int main(void)
{
    int q;
    scanf("%d%d",&n,&q);
    vi w;
    wh[1] = 1;
    for (int i = 2;i <= n;++i)
    {
        wh[i] = wh[i - 1];
        if (1ll * wh[i] * (wh[i] + 1) / 2 <= i)
            ++wh[i];
    }
    for (int i = 1;i <= n;++i)
        scanf("%d",&s[i]);
    for (int i = 1;i <= n;++i)
        w.pb(s[i]);
    sort(all(w));
    w.resize(unique(all(w)) - w.begin());
    const int SZ = w.size();
    for (int i = 1;i <= SZ;++i)
        v[i].pb(0);
    for (int i = 1;i <= n;++i)
        v[s[i] = lower_bound(all(w),s[i]) - w.begin() + 1].pb(i);
    for (int i = 1;i <= SZ;++i)
        v[i].pb(n + 1);
    Root[0] = -1;
    build(1,n,get(Root[0]));
    for (int i = 1;i <= n;++i)
    {
        int prev = Root[i - 1];
        Root[i] = -1;
        if (last[s[i]])
            update(1,n,last[s[i]],0,get(Root[i]),prev),prev = Root[i],Root[i] = -1;
        update(1,n,i,1,get(Root[i]),prev);
        last[s[i]] = i;
    }
    int ans = 0;
    while (q --)
    {
        int a,b;
        scanf("%d%d",&a,&b);

        int l = (a + ans) % n + 1;
        int r = (b + ans) % n + 1;
        ans = get(l,r);
        printf("%dn",ans);
    }
    return 0;
}