1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  5. #define CLR(x,y) memset(x,y,sizeof(x))
  6. #define LL long long
  7. #define LLU long long unsigned int
  8. typedef long long vlong;
  9. typedef unsigned long long uvlong;
  10.  
  11. const int MXN = 5005;
  12.  
  13. int N;
  14. int A[MXN], B[MXN];
  15. unordered_map<int, int> Map;
  16. int DP[MXN][MXN];
  17.  
  18. int call(int u, int len1, int len2){
  19.     if(u == N+1) return 0;
  20.     if(len1>len2) swap(len1, len2);
  21.     if(DP[u][len2] != -1) return DP[u][len2];
  22.  
  23.     int res = 0, ret;
  24.     /// Put A[u] to 1st lane:
  25.     ret = call(u+1, min(len1, A[u]), len2);
  26.     if(A[u]<=len1) ret++;
  27.     res = max(res, ret);
  28.  
  29.     /// Put A[u] to 2nd lane:
  30.     ret = call(u+1, len1, min(len2, A[u]));
  31.     if(A[u]<=len2) ret++;
  32.     res = max(res, ret);
  33.  
  34.     return DP[u][len2] = res;
  35. }
  36.  
  37. int main () {
  38.     scanf("%d",&N);
  39.     FOR(i,1,N){
  40.         scanf("%d",&A[i]);
  41.         B[i] = A[i];
  42.     }
  43.     sort(B+1,B+N+1);
  44.     int x = 0;
  45.     FOR(i,1,N){
  46.         if(Map.find(B[i]) == Map.end()){
  47.             Map[B[i]] = x++;
  48.         }
  49.     }
  50.     FOR(i,1,N){
  51.         A[i] = Map[A[i]];
  52.     }
  53.     CLR(DP, -1);
  54.     int res = call(1, 5000, 5000);
  55.     printf("%d\n",res);
  56.  
  57.     return 0;
  58. }