//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "区间MEX": {
        "prefix": "acm-2.8seg",
        "body": [
            "#pragma GCC optimize(\"O3,unroll-loops\")",
            "#include <iostream>",
            "using namespace std;",
            "const int N = 2e5 + 5; ",
            "int n, q, cnt, root[N];",
            "int ls[N * 40], rs[N * 40], min_pos[N * 40]; ",
            "int update(int pre, int l, int r, int x, int pos) {",
            "    int u = ++cnt;",
            "    ls[u] = ls[pre]; rs[u] = rs[pre]; ",
            "    if (l == r) {",
            "        min_pos[u] = pos;",
            "        return u;",
            "    }",
            "    int mid = (l + r) >> 1;",
            "    if (x <= mid) ls[u] = update(ls[pre], l, mid, x, pos);",
            "    else rs[u] = update(rs[pre], mid + 1, r, x, pos);",
            "    min_pos[u] = min(min_pos[ls[u]], min_pos[rs[u]]);",
            "    return u;",
            "}",
            "int query(int u, int l, int r, int limit_L) {",
            "    if (l == r) return l;",
            "    int mid = (l + r) >> 1;",
            "    if (min_pos[ls[u]] < limit_L) return query(ls[u], l, mid, limit_L);",
            "    else return query(rs[u], mid + 1, r, limit_L);",
            "}",
            "void solve() {",
            "    cin >> n >> q;",
            "    for (int i = 1, x; i <= n; ++i) {",
            "        cin >> x;",
            "        if (x > n + 1) {",
            "            root[i] = root[i - 1];",
            "        } else {",
            "            root[i] = update(root[i - 1], 0, n + 1, x, i);",
            "        }",
            "    }",
            "    while (q--) {",
            "        int l, r;",
            "        cin >> l >> r;",
            "        cout << query(root[r], 0, n + 1, l) << '\\n';",
            "    }",
            "}",
            "int main() {",
            "    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);",
            "    solve();",
            "    return 0;",
            "}"
        ],
        "description": "插入 区间MEX"
    }
}