1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int n, m, D;
int l, r, A[100005], hn[100005], hl[100005], root;
struct point_type {
    int mi[3], mx[3], a[3], ans, val, lc, rc;
} p[100005];
bool operator < (point_type a, point_type b) {
    return a.a[D] < b.a[D];
}
inline void push_up(int x) {
    int lc = p[x].lc, rc = p[x].rc;
    if (lc) {
        for (int i = 0; i < 3; ++i) {
            p[x].mi[i] = min(p[x].mi[i], p[lc].mi[i]);
            p[x].mx[i] = max(p[x].mx[i], p[lc].mx[i]);
        }
        p[x].ans = max(p[x].ans, p[lc].ans);
    }
    if (rc) {
        for (int i = 0; i < 3; ++i) {
            p[x].mi[i] = min(p[x].mi[i], p[rc].mi[i]);
            p[x].mx[i] = max(p[x].mx[i], p[rc].mx[i]);
        }
        p[x].ans = max(p[x].ans, p[rc].ans);
    }
}
double avg[3];
inline double sqr(double x) {
    return x * x;
}
int build(int l, int r, int d) {
    if (l > r) return 0;
    if (l == r) return l;
    avg[0] = avg[1] = avg[2] = 0;
    for (int i = 0; i < 3; ++i) {
        for (int j = l; j <= r; ++j)
            avg[i] += p[j].a[i];
        avg[i] /= (r - l + 1);
    }
    double fc, mxfc = -1;
    for (int i = 0; i < 3; ++i) {
        fc = 0;
        for (int j = l; j <= r; ++j)
            fc += sqr(avg[i] - p[j].a[i]);
        if (fc > mxfc) {
            mxfc = fc;
            D = i;
        }
    }
    int mid = (l + r) >> 1, nxtd = (d + 1) % 3;
    nth_element(p + l, p + mid, p + r + 1);
    p[mid].lc = build(l, mid - 1, nxtd);
    p[mid].rc = build(mid + 1, r, nxtd);
    push_up(mid);
    return mid;
}
int lstans = 0;
inline bool jud(int x) {
    if (p[x].mi[0] > l || p[x].mx[1] < l || p[x].mi[1] > r || p[x].mx[2] < r) return false;
    return true;
}
void query(int x) {
    if (p[x].mx[0] <= l && l <= p[x].mi[1] && p[x].mx[1] <= r && p[x].mi[2] >= r) {
        lstans = max(lstans, p[x].ans);
        return;
    }
    if (p[x].a[0] <= l && l <= p[x].a[1] && p[x].a[1] <= r && p[x].a[2] >= r) lstans = max(lstans, p[x].val);
    int lc = p[x].lc, rc = p[x].rc;
    if (lc && p[lc].ans > lstans && jud(lc)) query(p[x].lc);
    if (rc && p[rc].ans > lstans && jud(rc)) query(p[x].rc);
    return;
}
int main() {
    n = getint(); m = getint();
    for (int i = 1; i <= n; ++i) {
        A[i] = getint();
        hn[i] = n + 1;
        hl[i] = 0;
        p[i].mi[1] = p[i].mx[1] = p[i].a[1] = i;
        p[i].ans = p[i].val = A[i];
    }
    for (int i = 1, j = n; i <= n; ++i, --j) {
        p[i].mi[0] = p[i].mx[0] = p[i].a[0] = hl[A[i]] + 1;
        hl[A[i]] = i;
        p[j].mi[2] = p[j].mx[2] = p[j].a[2] = hn[A[j]] - 1;
        hn[A[j]] = j;
    }
    root = build(1, n, 0);
    int x, y;
    while (m--) {
        x = getint(); y = getint();
        l = (x + lstans) % n + 1;
        r = (y + lstans) % n + 1;
        if (l > r) swap(l, r);
        lstans = 0; query(root);
        printf("%d\n", lstans);
    }
    return 0;
}