Language: C++

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int MAXN = 5e5 + 1;

const int MAXS = 2e17;
int root[MAXN], root2[MAXN];

//Begin persistent segment tree
int lch[MAXS], rch[MAXS], sum2[MAXS], cnt;

int new_node (int val)
{
    assert(cnt < MAXS);
    sum2[cnt] = val;
    return cnt++;
}

int new_node (int l, int r, bool s)
{
    lch[cnt] = l;
    rch[cnt] = r;

    return new_node(s ? sum2[l] + sum2[r] : max(sum2[l], sum2[r]));
}

int build (int b, int e)
{
    if (b == e)
        return new_node(0);

    int m = (b + e) / 2;
    return new_node(build(b, m), build(m + 1, e), false);
}

int update2 (int v, int b, int e, int p, int val, bool s)
{
    if (b > p || e < p)
        return v;

    if (b == e)
        return new_node(val);

    int m = (b + e) / 2;
    int l = update2(lch[v], b, m, p, val, s),
        r = update2(rch[v], m + 1, e, p, val, s);

    return new_node(l, r, s);
}

int query (int v, int b, int e, int l, int r, bool s)
{
    if (e < l || b > r)
        return 0;

    if (l <= b && e <= r)
        return sum2[v];

    int m = (b + e) / 2;

    if (s)
        return  query(lch[v], b, m, l, r, s) + query(rch[v], m + 1, e, l, r, s);
    else
        return max(query(lch[v], b, m, l, r, s), query(rch[v], m + 1, e, l, r, s));
}

//End persistent segment tree


int n, a[MAXN], next_pos[MAXN], forw[MAXN], q, l, r, last[MAXN];
int pos[MAXN];

void update (int r, int a, int b)
{
    root2[a] = update2(r, 0, MAXN - 1, a, b, 0);
}

int dquery (int l, int r)
{
    return query(root[r + 1], 0, MAXN - 1, l + 1, r + 1, 1);
}

int32_t main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
    
    cin.sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    cin >> q;

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    root[0] = build(0, MAXN - 1);
    root2[n] = build(0, MAXN - 1);

    for (int i = 1; i <= n; ++i)
    {
        int r = root[i - 1];
        int a = ::a[i - 1];

        if (pos[a])
            r = update2(r, 0, MAXN - 1, pos[a], 0, 1);

        root[i] = update2(r, 0, MAXN - 1, i, 1, 1);
        pos[a] = i;
    }

    memset(forw, -1, sizeof forw);

    for (int i = n - 1; i >= 0; --i)
    {
        if (forw[a[i]] == -1)
        {
            update(root2[i + 1], i, MAXN - 2);
            next_pos[i] = MAXN - 2;
            last[i] = MAXN - 2;
        }
        else
        {
            int idx = forw[a[i]];
            int rot = update2(root2[i + 1], 0, MAXN - 1, idx, 0, 0);
            int r = next_pos[idx];
            next_pos[i] = idx;

            if (r == MAXN - 2 || r - idx != idx - i)
            {
                update(rot, i, r);
                last[i] = r;
            }
            else
            {
                update(rot, i, last[idx]);
                last[i] = last[idx];
            }
        }

        forw[a[i]] = i;
    }


    for (int i = 0; i < q; ++i)
    {
        cin >> l >> r;
        --l, --r;
        int ans = dquery(l, r);
        int cnt = query(root2[l], 0, MAXN - 1, l, r, 0);
        ans += cnt <= r;
        cout << ans << '\n';
    }
    return 0;
}

Compiler output:
/tmp/ccFj4eCR.o: in function `new_node(long long)':
a.cc:(.text+0xf): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0x4d): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0x5c): relocation truncated to fit: R_X86_64_PC32 against symbol `sum2' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0x6b): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0x76): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccFj4eCR.o
/tmp/ccFj4eCR.o: in function `new_node(long long, long long, bool)':
a.cc:(.text+0x94): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0xc1): relocation truncated to fit: R_X86_64_PC32 against symbol `rch' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0xe2): relocation truncated to fit: R_X86_64_PC32 against symbol `sum2' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0xf9): relocation truncated to fit: R_X86_64_PC32 against symbol `sum2' defined in .bss section in /tmp/ccFj4eCR.o
a.cc:(.text+0x115): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status