1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 const int maxn = 10000 + 10;
8
9 int n;
10
11 int a[maxn], l[maxn], r[maxn];
12 int g[maxn];
13
14 void LIS(int d[])
15 {
16 memset(g, 0x3f, sizeof(g));
17 for(int i = 0; i )
18 {
19 int k = lower_bound(g+1, g+1+n, a[i]) - g;
20 d[i] = k;
21 g[k] = a[i];
22 }
23 }
24
25 int main()
26 {
27 while(scanf("%d", &n) == 1)
28 {
29 for(int i = 0; i "%d", a + i);
30 LIS(l);
31 reverse(a, a + n);
32 LIS(r);
33
34 int ans = 1;
35 for(int i = 0; i 1-i]));
36 printf("%d\n", ans * 2 - 1);
37 }
38
39 return 0;
40 }