cf 1712 c

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}
#define DEBUG
#ifdef DEBUG
#define DEBUG_CMD(cmd)                                                                                                 \
    do {                                                                                                               \
        cmd;                                                                                                           \
    } while (false)
#else
#define DEBUG_CMD(cmd)                                                                                                 \
    do {                                                                                                               \
        ;                                                                                                              \
    } while (false)
#endif
#define _DEBUG_CMD(cmd)                                                                                                \
    do {                                                                                                               \
        ;                                                                                                              \
    } while (false)

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;

int t, n;
int a[100003];

int main(int argc, char **argv)
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        vector<int> ap[100003];
        for (int i = 0; i < n; ++i)
            scanf("%d", a + i);
        for (int i = n - 1; i >= 0; --i)
            ap[a[i]].push_back(i);

        int ub = a[n - 1];
        // unordered_set<int> gz;
        vector<int> gz(100003);
        for (int i = n - 1; i >= 0;) {
            int hit = 0;
            if (a[i] > ub) {
                for (int k = 0; k <= i; ++k)
                    // gz.insert(a[k]);
                    gz[a[k]] = 1;
                break;
            }
            int j, end = ap[a[i]].back();
            for (j = i; j >= end; --j) {
                if (a[j] != a[i]) {
                    hit = 1;
                    break;
                }
            }
            if (hit) {
                for (int k = 0; k <= i; ++k)
                    // gz.insert(a[k]);
                    gz[a[k]] = 1;
                break;
            } else {
                ub = a[i];
                i = j;
            }
        }
        int ret = 0;
        for (int i = 1; i <= n; ++i) {
            ret += gz[i];
        }
        printf("%d\n", ret);
        // printf("%lu\n", gz.size());
    }
    return 0;
};