# HackerEarth Min difference queries problem solution

In this HackerEarth Min differene queries problem solution, You have a sequence a of length n and you want to answer q queries determined by 2 integers l and r. You take all numbers present in subsequence (al, al+1,...,ar, let them be b1,b2,...,bt and number of occurrences of each number in this subsequence be c1,c2,...,ct respectively. The answer for per query is equal to min|ci - cj| for 1 <= i < j <= t or 1 if t = 1.

## 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("%d\n",ans);    }    return 0;}`

### Second solution

`#include "bits/stdc++.h"using namespace std; #define MAX 100002 int n;int q; vector<int> v; #define MAGIC 333#define MM 500int u[MAGIC][MM]; int sz[MAGIC];  bool ex[MAX]; vector<int> vv; vector<int> idx[MAX]; set<int> s;  int main() {    cin >> n >> q;    assert(1<=n&&n<=100000);    assert(1<=q&&q<=100000);    for (int i = 0; i < n; i++) {        int a;        scanf("%d", &a);        assert(1<=a);        assert(a<=1000000000);        v.push_back(a);        vv.push_back(a);    }    sort(vv.begin(), vv.end());    for (int i = 0; i < v.size(); i++) {        v[i] = lower_bound(vv.begin(), vv.end(), v[i]) - vv.begin();        idx[v[i]].push_back(i);    }    for (int i = 0; i < n; i+=MAGIC) {        memset(ex, false, sizeof(ex));        for (int j = i; j < n; j++) {            if (ex[v[j]])continue;            ex[v[j]] = true;            u[i / MAGIC][sz[i / MAGIC]] = v[j];            sz[i / MAGIC]++;            if(sz[i/MAGIC]==MM)break;        }    }    int las = 0;    while (q--) {        int a,b;        scanf("%d%d", &a, &b);        assert(1<=a&&a<=n&&1<=b&&b<=n);        int l = (a + las) % n + 1;        int r = (b + las) % n + 1;        l--;        r--;        assert(0<=l&&0<=r);        int belong = l / MAGIC;        s.clear();        bool en = false;        for (int i = 0; i < sz[belong]; i++) {              int val = u[belong][i];            int lef = lower_bound(idx[val].begin(), idx[val].end(), l) - idx[val].begin();            int rig = upper_bound(idx[val].begin(), idx[val].end(), r) - idx[val].begin();            int oc = rig - lef;            if (oc == 0)continue;            if (s.count(oc)) {                en = true;                break;            }            s.insert(oc);        }        if (en) {            puts("0");            las = 0;            continue;        }        if (s.size() == 1) {            puts("-1");            las = -1;            continue;        }        int ans = INT_MAX;        int pr = -1;        for (auto el : s) {            if (pr != -1) {                ans = min(ans, el - pr);            }            pr = el;        }        printf("%d\n", ans);        las = ans;    }    return 0;}`