1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

#include <iostream>

#include <algorithm>

#include <stack>

 

using namespace std;

 

int arr[1000000];

int dp[1000000];

int in[1000000];

 

int main() {

    int N;

    int result = 0;

    stack<int> s;

    cin >> N;

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

        cin >> in[i];

        auto pos = lower_bound(arr, arr + result, in[i]);

        *pos = in[i];

 

        if (pos == arr + result) {

            result++;

            dp[i] = result;

        } else

            dp[i] = pos – arr + 1;

    }

    cout << result << “\n”;

    for (int i = N – 1; i >= 0 and result > 0; ––i) {

        if (dp[i] == result) {

            s.push(in[i]);

            ––result;

        }

    }

    while (!s.empty()) {

        cout << s.top() << ” “;

        s.pop();

    }

    return 0;

}