1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 #include <string.h>
 6 
 7 using namespace std;
 8 
 9 const int MAXN = 1e5 + 10;
10 int n = 1, a[MAXN], d[MAXN], dp[MAXN];
11 
12 int main()
13 {
14     int ans1 = 0, ans2 = 0; 
15     while(scanf("%d", &a[n]) != EOF)
16     {
17         ++n; 
18     }
19     --n;
20     for(int i = 1; i <= n; i++)
21     {
22         d[i] = 1;
23         for(int j = 1; j < i; j++)
24         {
25             if(a[j] >= a[i])
26             {
27                 d[i] = max(d[i], d[j] + 1);
28             }
29         }
30         if(ans1 < d[i])
31         {
32             ans1 = d[i];
33         }
34     }
35     for(int i = 1; i <= n; i++)
36     {
37         dp[i] = 1;
38         for(int j = 1; j < i; j++)
39         {
40             if(a[j] < a[i])
41             {
42                 dp[i] = max(dp[i], dp[j] + 1);
43             }
44         }
45         if(ans2 < dp[i])
46         {
47             ans2 = dp[i];
48         }
49     }
50     cout << ans1 << endl;
51     cout << ans2 << endl;
52     return 0;
53 }

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 #include <string.h>
 6 
 7 using namespace std;
 8 
 9 const int MAXN = 1e5 + 10;
10 int n = 1, a[MAXN], d[MAXN], dp[MAXN], ans1 = 0, ans2 = 0, mid, l, r;
11 
12 int main()
13 { 
14     while(scanf("%d", &a[n]) != EOF)
15     {
16         ++n; 
17         continue;
18     }
19     --n;
20     d[1] = a[1];
21     dp[1] = a[1];
22     ans1 = ans2 = 1;
23     for(int i = 2; i <= n; i++)
24     {
25         if(a[i] <= d[ans1])
26         {
27             ans1++;
28             d[ans1] = a[i];
29         }
30         else
31         {
32             l = 1, r = ans1;
33             while(l < r)
34             {
35                 mid = (l + r) / 2;
36                 if(a[i] > d[mid])
37                 {
38                     r = mid;
39                 }
40                 else
41                 {
42                     l = mid + 1;
43                 }
44             }
45             d[l] = a[i];
46         }
47     }    
48     
49     for(int i = 2; i <= n; i++)
50     {
51         if(a[i] > dp[ans2])
52         {
53             ans2++;
54             dp[ans2] = a[i];
55         }
56         else
57         {
58             l = 1, r = ans2;
59             while(l < r)
60             {
61                 mid = (l + r) / 2;
62                 if(a[i] <= dp[mid])
63                 {
64                     r = mid;
65                 }
66                 else
67                 {
68                     l = mid + 1;
69                 }
70             } 
71             dp[l] = a[i];
72         }
73     }    
74     cout << ans1 << endl;
75     cout << ans2 << endl;
76     return 0;
77 }