rt,这个复杂度再差也不能全T吧，样例已过

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 10;
bool flag;
int T, n, q, l, r, ans, a[maxn], st[maxn][25];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", a + i);
			st[i - 1][0] = i;
		}
		for (int j = 1; (1 << j) <= n; j++) {
			for (int i = 1; i <= n; i++) {
				st[i][j] = st[st[i][j - 1]][j - 1];
			}
		}
		scanf("%d", &q);
		while (q--) {
			scanf("%d %d", &l, &r);
			ans = r - l + 1;
			while (l <= r) {
				if (l > r) {
					ans = 0;
					break;
				}
				flag = 1;
				for (int i = 18; ~i; i--) {
					if (st[l][i] <= r && a[st[l][i]] == a[l]) {
						flag = 0;
						ans -= st[l][i] - l + 1;
						l = st[l][i] + 1;
					}
				}
				if (flag) l++;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}