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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
template <class T>
inline bool rd(T &ret) {
    char c; int sgn;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && (c<'0' || c>'9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}
template <class T>
inline void pt(T x) {
    if (x <0) { putchar('-'); x = -x; }
    if (x>9) pt(x / 10);
    putchar(x % 10 + '0');
}
using namespace std;
const int N = 200100;
const int inf = 1e9;
const int SIZE = 447;
int a[N], n, Q, ans;
int block[N / SIZE + 5][SIZE];
void init() {
    rd(n); rd(Q);
    int  b = 0, j = 0;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX