[Gold 3] 11054번 가장 긴 바이토닉 부분 수열

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] a = br.readLine().split(" ");
        String[] ra = new String[n];
        int[] up = new int[n];
        int[] down = new int[n];
        int[] bt = new int[n];
        int ans = 0;
        
        for(int i=0; i<n; i++) { ra[i] = a[n-1-i]; }
        
        for(int i=0; i<n; i++) {
            up[i] = 1;
            down[i] = 1;
            for(int j=0; j<i; j++) {
                if(Integer.parseInt(a[j])<Integer.parseInt(a[i]) && up[j]>=up[i]) {
                    up[i]++;
                }
                
                if(Integer.parseInt(ra[j])<Integer.parseInt(ra[i]) && down[j]>=down[i]) {
                    down[i]++;
                }
            }
        }
        
        for(int i=0; i<n; i++) { bt[i] = up[i]+down[n-1-i]-1; }
        
        for(int i=0; i<n; i++) {
            if(ans<bt[i]) { ans = bt[i]; }
        }
        
        System.out.println(ans);
    }
}