1+ import java .util .Scanner ;
2+
3+ /**
4+ *
5+ * @author Afrizal Fikri (https://github.com/icalF)
6+ *
7+ */
8+ public class LongestIncreasingSubsequence {
9+ public static void main (String []args )throws Exception {
10+
11+ Scanner sc =new Scanner (System .in );
12+ int n =sc .nextInt ();
13+
14+ int ar [] =new int [n ];
15+ for (int i =0 ;i <n ;i ++) {
16+ ar [i ] =sc .nextInt ();
17+ }
18+
19+ System .out .println (LIS (ar ));
20+ }
21+
22+ private static int upperBound (int []ar ,int l ,int r ,int key ) {
23+ while (l <r -1 ) {
24+ int m = (l +r ) /2 ;
25+ if (ar [m ] >=key )
26+ r =m ;
27+ else
28+ l =m ;
29+ }
30+
31+ return r ;
32+ }
33+
34+ public static int LIS (int []array ) {
35+ int N =array .length ;
36+ if (N ==0 )
37+ return 0 ;
38+
39+ int []tail =new int [N ];
40+ int length =1 ;// always points empty slot in tail
41+
42+ tail [0 ] =array [0 ];
43+ for (int i =1 ;i <N ;i ++) {
44+
45+ // new smallest value
46+ if (array [i ] <tail [0 ])
47+ tail [0 ] =array [i ];
48+
49+ // array[i] extends largest subsequence
50+ else if (array [i ] >tail [length -1 ])
51+ tail [length ++] =array [i ];
52+
53+ // array[i] will become end candidate of an existing subsequence or
54+ // Throw away larger elements in all LIS, to make room for upcoming grater elements than array[i]
55+ // (and also, array[i] would have already appeared in one of LIS, identify the location and replace it)
56+ else
57+ tail [upperBound (tail , -1 ,length -1 ,array [i ])] =array [i ];
58+ }
59+
60+ return length ;
61+ }
62+ }