1. #include<bits/stdc++.h>
2. using namespace std;
3.  
4. #define greater greater123123
5. #define less less123123
6.  
7. const int N = 3e5+100;
8.  
9. int a[N];
10.  
11. struct Seg{
12.     int seg[4*N];
13.  
14.     Seg(){
15.         memset(seg, 0, sizeof seg);
16.     }
17.  
18.     int get(int l, int r, int s=0, int e=N, int id=1){
19.         if(r<=s || e<=l)
20.             return 0;
21.         if(l<=s && e<=r)
22.             return seg[id];
23.         int mid = (s + e)/2;
24.         return max(get(l, r, s, mid, 2*id), get(l, r, mid, e, 2*id+1));
25.     }
26.  
27.     void upd(int x, int val, int s=0, int e=N, int id=1){
28.         if(s>x || e<=x)
29.             return;
30.         if(e-s == 1){
31.             seg[id] = max(seg[id], val);
32.             return;
33.         }
34.         int mid = (s + e)/2;
35.         upd(x, val, s, mid, 2*id);
36.         upd(x, val, mid, e, 2*id+1);
37.         seg[id] = max(seg[2*id], seg[2*id+1]);
38.     }
39. } greater, less;
40.  
41. int main(){
42.         ios_base::sync_with_stdio(false);cin.tie(NULL);
43.     int n;cin >> n;
44.     for(int i=0 ; i<n ; i++)
45.         cin >> a[i];
46.     reverse(a, a+n);
47.     int ans=0;
48.     for(int i=0 ; i<n ; i++){
49.         // <= a[i]
50.         int cur1 = less.get(0, a[i]+1) + 1;
51.         ans = max(ans, cur1);
52.         // >= a[i]
53.         int cur2 = greater.get(a[i], N) + 1;
54.         greater.upd(a[i], cur1);
55.         less.upd(a[i], cur2);
56.     }
57.  
58.     cout << ans << "\n";
59. }
60.