Chronological Improvements

The founder has received a report containing a sequence of improvements. Each improvement is identified by a unique number; however, the order in which the improvements were reported does not necessarily match their numerical order. In order to present the improvements in a coherent timeline, the founder requires that the final report list the improvements in strictly increasing order (i.e. in ascending order of their improvement numbers).

This can be achieved in two steps:

1. Each consultant, who initially receives a part of the report, selects a subsequence (preserving the original order) of improvements such that the chosen numbers are in strictly increasing order.
2. Each manager then merges the reports from their subordinates. Since the order within each subordinate’s report is preserved, the manager can arbitrarily interleave these sequences. The objective is that the final merged report also has improvements arranged in strictly increasing order.

Formally, given a sequence of improvement numbers \(a_1, a_2, \dots, a_n\) (in the order in which they were reported), your task is to determine the length of the longest strictly increasing subsequence (LIS). This length represents the maximum number of improvements that can be reordered to meet the founder's requirement.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) representing the number of improvements.
2. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) where each \(a_i\) represents an improvement number.

outputFormat

Output a single integer: the length of the longest strictly increasing subsequence that can be formed from the reported improvements.

sample

5
1 2 3 4 5

5