UVa 11456 - Trainsorting

// UVa 11456 - Trainsorting

#include <iostream>
using namespace std;

#define integer signed long long int

int main() {
	int t;
	for (cin >> t; t; t--) {
		int n;
		cin >> n;
		integer a[2001];
		int lis[2001], lds[2001], sol = 1;
		for (int i = 0; i < n; i++)
			cin >> a[i];
		lis[n] = 0;
		lds[n] = 0;
		for (int i = n - 1; i >= 0; i--) {
			lis[i] = 0;
			lds[i] = 0;
			for (int j = i + 1; j < n; j++) {
				if (a[i] < a[j] && lis[j] > lis[i])
					lis[i] = lis[j];
				if (a[i] > a[j] && lds[j] > lds[i])
					lds[i] = lds[j];
			}
			lis[i]++;
			lds[i]++;
			if (lis[i] + lds[i] > sol)
				sol = lis[i] + lds[i];
		}
		cout << sol - 1 << endl;
	}
	return 0;
}