#include <bits/stdc++.h>
using namespace std;
void Print(int _x) { printf("%d\n", _x); }
void Print(long long _x) { printf("%lld\n", _x); }
template <typename T>
void Print(T _a[], int _s, int _t) {
  for (int i = _s; i <= _t; i++) cout << _a[i] << " ";
  cout << endl;
}
struct InputReader {
  static const int bs = 100000;
  char buf[bs];
  int p;
  inline InputReader() : p(bs) {}
  inline void Flush() {
    p = 0;
    fread(buf, 1, bs, stdin);
  }
  inline char C() {
    if (p >= bs) Flush();
    return buf[p++];
  }
  int Getnum() {
    char ch = C();
    while (ch < '0' || ch > '9') ch = C();
    return (int)(ch - '0');
  }
  inline int operator()() {
    int ans = 0;
    char ch = C();
    int fu = 1;
    while (ch < '0' || ch > '9') {
      if (ch == '-') fu = -1;
      ch = C();
    }
    while (ch >= '0' && ch <= '9') {
      ans *= 10;
      ans += ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  long long Readll() {
    long long ans = 0LL;
    long long fu = 1;
    char ch = C();
    while (ch < '0' || ch > '9') {
      if (ch == '-') fu = -1;
      ch = C();
    }
    while (ch >= '0' && ch <= '9') {
      ans *= 10LL;
      ans += ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  inline void Readstring(string &x) {
    x.clear();
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch)) ch = C();
    while (isdigit(ch) || isalpha(ch)) {
      x += ch;
      ch = C();
    }
  }
  inline void Readalpha(char &c) {
    c = C();
    while (!isalpha(c)) c = C();
  }
  inline char Specialread() {
    char ch = C();
    while (!isalpha(ch)) ch = C();
    return ch;
  }
} In;
inline void Read(int &x) { x = In(); }
inline void Read(int &x, int &y) {
  x = In();
  y = In();
}
inline void Read(int &x1, int &x2, int &x3) {
  x1 = In();
  x2 = In();
  x3 = In();
}
inline void Read(int &x1, int &x2, int &x3, int &x4) {
  x1 = In();
  x2 = In();
  x3 = In();
  x4 = In();
}
inline void Read(long long &x) { x = In.Readll(); }
inline void Read(long long &x, long long &y) {
  x = In.Readll();
  y = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3, long long &x4) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
  x4 = In.Readll();
}
clock_t _starttime, _endtime;
inline void FILEIO() {}
inline void END() { exit(0); }
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
int n;
int dat[2010];
int cnt0[2010], cnt1[2010];
int ans = 1;
int sum0(int l, int r) { return cnt0[r] - cnt0[l - 1]; }
int sum1(int l, int r) { return cnt1[r] - cnt1[l - 1]; }
int dp[2010][2010];
int maxdp[2010][2010];
void Dp() {
  memset(maxdp, 0, sizeof(maxdp));
  for (register int(i) = 1; (i) <= (n); (i)++) {
    dp[i][i] = 1;
    int nowmax = 1;
    maxdp[i][i] = 1;
    for (register int(j) = (i + 1); (j) <= (n); (j)++) {
      if (dat[j] == 0) {
        dp[i][j] = nowmax + 1;
      } else {
        dp[i][j] = sum1(i, j);
      }
      if (nowmax < dp[i][j]) nowmax = dp[i][j];
      ;
      maxdp[i][j] = nowmax;
    }
  }
}
int Cal(int l, int r) {
  int ans = cnt0[l - 1] + maxdp[l][r] + cnt1[n] - cnt1[r];
  return ans;
}
int main() {
  FILEIO();
  Read(n);
  for (register int(i) = 1; (i) <= (n); (i)++) {
    Read(dat[i]);
    dat[i]--;
  }
  memset(cnt0, 0, sizeof(cnt0));
  memset(cnt1, 0, sizeof(cnt1));
  for (register int(i) = 1; (i) <= (n); (i)++) {
    cnt0[i] = cnt0[i - 1] + (dat[i] == 0);
    cnt1[i] = cnt1[i - 1] + (dat[i] == 1);
  }
  Dp();
  for (register int(i) = 1; (i) <= (n); (i)++)
    for (register int(j) = (i); (j) <= (n); (j)++) {
      int tans = Cal(i, j);
      if (ans < tans) ans = tans;
      ;
    }
  printf("%d\n", ans);
  END();
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

A dragon symbolizes wisdom, power and wealth. On Lunar New Year's Day, people model a dragon with bamboo strips and clothes, raise them with rods, and hold the rods high and low to resemble a flying dragon.

A performer holding the rod low is represented by a 1, while one holding it high is represented by a 2. Thus, the line of performers can be represented by a sequence a1, a2, ..., an.

Little Tommy is among them. He would like to choose an interval [l, r] (1 ≤ l ≤ r ≤ n), then reverse al, al + 1, ..., ar so that the length of the longest non-decreasing subsequence of the new sequence is maximum.

A non-decreasing subsequence is a sequence of indices p1, p2, ..., pk, such that p1 < p2 < ... < pk and ap1 ≤ ap2 ≤ ... ≤ apk. The length of the subsequence is k.

Input

The first line contains an integer n (1 ≤ n ≤ 2000), denoting the length of the original sequence.

The second line contains n space-separated integers, describing the original sequence a1, a2, ..., an (1 ≤ ai ≤ 2, i = 1, 2, ..., n).

Output

Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.

Examples

Input

4
1 2 1 2


Output

4


Input

10
1 1 2 2 2 1 1 2 2 1


Output

9

Note

In the first example, after reversing [2, 3], the array will become [1, 1, 2, 2], where the length of the longest non-decreasing subsequence is 4.

In the second example, after reversing [3, 7], the array will become [1, 1, 1, 1, 2, 2, 2, 2, 2, 1], where the length of the longest non-decreasing subsequence is 9.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void Print(int _x) { printf("%d\n", _x); }
void Print(long long _x) { printf("%lld\n", _x); }
template <typename T>
void Print(T _a[], int _s, int _t) {
  for (int i = _s; i <= _t; i++) cout << _a[i] << " ";
  cout << endl;
}
struct InputReader {
  static const int bs = 100000;
  char buf[bs];
  int p;
  inline InputReader() : p(bs) {}
  inline void Flush() {
    p = 0;
    fread(buf, 1, bs, stdin);
  }
  inline char C() {
    if (p >= bs) Flush();
    return buf[p++];
  }
  int Getnum() {
    char ch = C();
    while (ch < '0' || ch > '9') ch = C();
    return (int)(ch - '0');
  }
  inline int operator()() {
    int ans = 0;
    char ch = C();
    int fu = 1;
    while (ch < '0' || ch > '9') {
      if (ch == '-') fu = -1;
      ch = C();
    }
    while (ch >= '0' && ch <= '9') {
      ans *= 10;
      ans += ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  long long Readll() {
    long long ans = 0LL;
    long long fu = 1;
    char ch = C();
    while (ch < '0' || ch > '9') {
      if (ch == '-') fu = -1;
      ch = C();
    }
    while (ch >= '0' && ch <= '9') {
      ans *= 10LL;
      ans += ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  inline void Readstring(string &x) {
    x.clear();
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch)) ch = C();
    while (isdigit(ch) || isalpha(ch)) {
      x += ch;
      ch = C();
    }
  }
  inline void Readalpha(char &c) {
    c = C();
    while (!isalpha(c)) c = C();
  }
  inline char Specialread() {
    char ch = C();
    while (!isalpha(ch)) ch = C();
    return ch;
  }
} In;
inline void Read(int &x) { x = In(); }
inline void Read(int &x, int &y) {
  x = In();
  y = In();
}
inline void Read(int &x1, int &x2, int &x3) {
  x1 = In();
  x2 = In();
  x3 = In();
}
inline void Read(int &x1, int &x2, int &x3, int &x4) {
  x1 = In();
  x2 = In();
  x3 = In();
  x4 = In();
}
inline void Read(long long &x) { x = In.Readll(); }
inline void Read(long long &x, long long &y) {
  x = In.Readll();
  y = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3, long long &x4) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
  x4 = In.Readll();
}
clock_t _starttime, _endtime;
inline void FILEIO() {}
inline void END() { exit(0); }
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
int n;
int dat[2010];
int cnt0[2010], cnt1[2010];
int ans = 1;
int sum0(int l, int r) { return cnt0[r] - cnt0[l - 1]; }
int sum1(int l, int r) { return cnt1[r] - cnt1[l - 1]; }
int dp[2010][2010];
int maxdp[2010][2010];
void Dp() {
  memset(maxdp, 0, sizeof(maxdp));
  for (register int(i) = 1; (i) <= (n); (i)++) {
    dp[i][i] = 1;
    int nowmax = 1;
    maxdp[i][i] = 1;
    for (register int(j) = (i + 1); (j) <= (n); (j)++) {
      if (dat[j] == 0) {
        dp[i][j] = nowmax + 1;
      } else {
        dp[i][j] = sum1(i, j);
      }
      if (nowmax < dp[i][j]) nowmax = dp[i][j];
      ;
      maxdp[i][j] = nowmax;
    }
  }
}
int Cal(int l, int r) {
  int ans = cnt0[l - 1] + maxdp[l][r] + cnt1[n] - cnt1[r];
  return ans;
}
int main() {
  FILEIO();
  Read(n);
  for (register int(i) = 1; (i) <= (n); (i)++) {
    Read(dat[i]);
    dat[i]--;
  }
  memset(cnt0, 0, sizeof(cnt0));
  memset(cnt1, 0, sizeof(cnt1));
  for (register int(i) = 1; (i) <= (n); (i)++) {
    cnt0[i] = cnt0[i - 1] + (dat[i] == 0);
    cnt1[i] = cnt1[i - 1] + (dat[i] == 1);
  }
  Dp();
  for (register int(i) = 1; (i) <= (n); (i)++)
    for (register int(j) = (i); (j) <= (n); (j)++) {
      int tans = Cal(i, j);
      if (ans < tans) ans = tans;
      ;
    }
  printf("%d\n", ans);
  END();
}

```