$1 \le t \le 10000, 1 \le \sum n \le 200000$

怎么优化？

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a[200010], fMin[200010][20], fMax[200010][20], lg[200010];
template <typename T> inline void read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}
inline void solve() {
	read(n);
	for (int i = 1; i <= n; i ++ ) read(a[i]);
	memset(fMax, 0, sizeof fMax);
	memset(fMin, 0, sizeof fMin);
	memset(lg, 0, sizeof lg);
	for (int i = 2; i <= n; i ++ ) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; i <= n; i ++ ) {
		fMax[i][0] = a[i];
		fMin[i][0] = a[i];
	}
	for (int j = 1; j <= lg[n]; j ++ ) {
		for (int i = 1; i + (1<<j) - 1 <= n; i ++ ) {
			fMax[i][j] = max(fMax[i][j - 1], fMax[i + (1<<(j-1))][j - 1]);
			fMin[i][j] = min(fMin[i][j - 1], fMin[i + (1<<(j-1))][j - 1]);
		}
	}
	int l = 1, r = n;
	while (l + 2 < r) {
		int k = lg[r - l + 1];
		int Max = max(fMax[l][k], fMax[r - (1<<k) + 1][k]);
		int Min = min(fMin[l][k], fMin[r - (1<<k) + 1][k]);
		if (a[l] == Max || a[l] == Min) l ++ ;
		else if (a[r] == Max || a[r] == Min) r -- ;
		else {
			printf("%d %d\n", l, r);
			return;
		}
	}
	puts("-1");
}
int main() {
	int T;
	read(T);
	while (T -- ) solve();
	return 0;
}