27、接竹竿

小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。

游戏规则是：每张牌上有一个点数 v，将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌，则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本⾝）。

小杨同学现在有一个长度为n的卡牌序列A，其中每张牌的点数为Aᵢ (1≤i≤n)。小杨同学有Q次询问。第 i（1≤i≤Q ）次询问时，小杨同学会给出 Lᵢ Rᵢ，小杨同学想知道如果用下标在[Lᵢ, Rᵢ]的所有卡牌按照下标顺序玩“接竹竿”的游戏，最后队列中剩余的牌数。

【输入描述】

第一行包含一个正整数T，表示测试数据组数。

对于每组测试数据，第一行包含一个正整数n，表示卡牌序列A的长度。

第二行包含N个正整数A₁ , A₂ , ..., Aₙ ，表示卡牌的点数。

第三行包含一个正整数 Q，表示询问次数。

接下来 Q 行，每行两个正整数 Lᵢ, Rᵢ，表示一组询问。

N≤1e5

【输出描述】

对于每组数据，输出Q行。第i行（1≤i≤Q ）输出一个非负整数，表示第 i 次询问的答案。

【输入样例】

1
6
1 2 2 3 1 3
4
1 3
1 6
1 5
5 6

【输出样例】

1
1
0
2

//输出说明
对于第一次询问，小杨同学会按照1,2,2的顺序放置卡牌，在放置最后一张卡牌时，两张点数为2 的卡牌会被收⾛，因此最后队列中只剩余一张点数为 1 的卡牌。
对于第二次询问，队列变化情况为：{}->{1}->{1,2}->{1,2,3}->{1}->{1,3}->{1,3,1}->{}->{3}。因此最后队列中只剩余一张点数为 3 的卡牌。

【参考程序】

// 爱码岛编程 P10264
#include <bits/stdc++.h>
using namespace std;

int T, N, Q, L, R;
int arr[100005], pos[100005];

int main() {
    cin >> T;
    while (T--) {
        cin >> N;
        // 1 2 2 3 1 3
        for (int i = 1; i <= N; i++)
            cin >> arr[i];
        int indx[15] = {0};
        for (int i = N; i >= 1; i--) {
            // pos[i]表示第i个元素在其后第一次出现的位置
            pos[i] = indx[arr[i]];
            indx[arr[i]] = i;
        }
        
        // 5 3 0 6 0 0
        cin >> Q;
        while (Q--) {
            cin >> L >> R;
            int cnt = 0;
            for (int j = L; j <= R; j++) {
                if (pos[j] >= L && pos[j] <= R)
                    j = pos[j];
                else
                    cnt++;
            }
            cout << cnt << endl;
        }
    }
    return 0;
}