Minimum Platforms Required at Milan Central Station

Silvia is at Milan Central Station and has observed that there are many platforms. Believing that some of these platforms are redundant, she wishes to determine the minimum number of platforms needed so that all trains can be accommodated without any departure being blocked.

The station operates on a peculiar timetable that repeats every two days: all n trains arrive on one day and then depart on the following day. Importantly, no train departs before every train has arrived. This means that the trains arrive in order (from 1 to n) and then later depart in a given permutation.

There is one more constraint: the platform is long enough that any number of trains may line up. However, if train x enters a platform before train y on the same platform, then x is not allowed to depart until after y has departed. In other words, on a single platform, the departure order must be the reverse of the arrival order.

Given that the arrival order is fixed (trains 1 through n in order) and the departure order is provided as a permutation of these numbers, the problem reduces to partitioning this departure sequence into subsequences where each subsequence is strictly decreasing. A key insight is that a set of trains can share a platform if and only if their departure times, when listed in the same order as their arrivals, form a strictly decreasing sequence.

It is well known (by Dilworth's theorem) that the minimum number of such decreasing subsequences required to partition any sequence is equal to the length of the longest increasing subsequence (LIS) in that sequence. Therefore, the answer to Silvia's problem is to compute the length of the longest increasing subsequence of the departure order.

Task: Given an integer n and a permutation of the numbers from 1 to n representing the departure order (in the order of arrival), determine the minimum number of platforms needed so that all trains can be scheduled without any departure being blocked.

inputFormat

The input consists of two lines:

1. The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of trains.
2. The second line contains n space-separated integers which form a permutation of the numbers from 1 to n, representing the departure order corresponding to the arrival order (trains arriving from 1 to n in order).

outputFormat

Output a single integer – the minimum number of platforms required so that no train is blocked by another train that arrived before it.

sample

3
3 2 1

1