Cod sursă (job #502561)

#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin ("s2c.in");
ofstream cout ("s2c.out");

int t, n, m;

short dp[2005][2005], v[2005];
pair <int, int> dist[2005];

bool comp(pair <int, int> a, pair <int, int> b) {
  if(a.first == b.first)
    return a.second > b.second;
  return a.first < b.first;
}

int main() {
  cin >> t;
  for(; t; t--) {
    cin >> n;
    m = 0;
    for(int i = 1; i <= n; i++) {
      cin >> v[i];
      dist[i] = {v[i], i};
    }
    sort(dist + 1, dist + n + 1, comp);
    for(int i = 1; i <= n; i++)
      v[dist[i].second] = i;
    for(int i = 1; i <= n; i++)
      dp[1][v[i]] = 1;
    for(int i = 2; i <= n; i++) {
      for(int j = 1; j <= n; j++)
        dp[i][j] = 1;
      for(int j = 1; j < i; j++)
        dp[i][v[j]] = 1 + dp[j][v[i]];
      for(int j = 1; j <= n; j++)
        dp[i][j] = max(dp[i][j], dp[i][j - 1]);
    }
    short ans = 0;
    for(int i = 1; i <= n; i++)
      ans = max(ans, dp[i][n]);
    cout << ans << "\n";
  }
  return 0;
}