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.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 public class _934C {

 }

 */
public class _934C {
  public void solve() throws FileNotFoundException {
    InputStream inputStream = System.in;

    InputHelper in = new InputHelper(inputStream);

    // actual solution
    int n = in.readInteger();


    int[] a = new int[n];


    for (int i = 0; i < n; i++) {
      a[i] = in.readInteger();
    }


    int[] ones = new int[n];

    if (a[0] == 1) {
      ones[0] = 1;
    }

    for (int i = 1; i < n; i++) {
      if (a[i] == 1) {
        ones[i] = ones[i - 1] + 1;
      } else {
        ones[i] = ones[i - 1];
      }
    }

    int[] twos = new int[n];

    if (a[n - 1] == 2) {
      twos[n - 1] = 1;
    }

    for (int i = n - 2; i >= 0; i--) {
      if (a[i] == 2) {
        twos[i] = twos[i + 1] + 1;
      } else {
        twos[i] = twos[i + 1];
      }
    }

    int ans = Math.max(ones[n - 1], twos[0]);

    for (int i = 0; i < n; i++) {
      int cans = twos[i];
      if (i > 0) {
        cans += ones[i - 1];
      }

      ans = Math.max(ans, cans);

      int o = 0;
      int t = 0;
      int min = 0;
      for (int j = i; j < n; j++) {
        if (a[j] == 1) {
          o++;
        } else {
          t++;
        }
        if (o > t) {
          min = Math.max(min, o - t);
        }
      }

      cans += min;

      o = 0;
      t = 0;
      min = 0;
      for (int j = i - 1; j >= 0; j--) {
        if (a[j] == 1) {
          o++;
        } else {
          t++;
        }
        if (o < t) {
          min = Math.max(min, t - o);
        }
      }

      cans += min;

      ans = Math.max(cans, ans);
    }
    
    System.out.println(ans);
    // end here
  }

  public static void main(String[] args) throws FileNotFoundException {
    (new _934C()).solve();
  }

  class InputHelper {
    StringTokenizer tokenizer = null;
    private BufferedReader bufferedReader;

    public InputHelper(InputStream inputStream) {
      InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
      bufferedReader = new BufferedReader(inputStreamReader, 16384);
    }

    public String read() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String line = bufferedReader.readLine();
          if (line == null) {
            return null;
          }
          tokenizer = new StringTokenizer(line);
        } catch (IOException e) {
          e.printStackTrace();
        }
      }

      return tokenizer.nextToken();
    }

    public Integer readInteger() {
      return Integer.parseInt(read());
    }

    public Long readLong() {
      return Long.parseLong(read());
    }
  }
}
