1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

#include <iostream>

#include <algorithm>

 

using namespace std;

 

int arr[1000000];

 

int main() {

    int N;

    int result = 0;

    cin >> N;

    for (int i = 0; i < N; i++) {

        int num;

        cin >> num;

        auto pos = lower_bound(arr, arr + result, num);

        *pos = num;

        if (pos == arr + result)

            result++;

    }

    cout << result;

    return 0;

}