Partitioning into Two Strictly Increasing Subsequences

Given an even length sequence of integers of length \(N\) (where \(N\) is even), determine if it is possible to partition the sequence into two subsequences, each of length \(\frac{N}{2}\), such that both subsequences are strictly increasing. The subsequences must preserve the original order of elements. Formally, if the two subsequences are \(a_1,a_2,\dots,a_{N/2}\) and \(b_1,b_2,\dots,b_{N/2}\), then they must satisfy

[ a_1 < a_2 < \cdots < a_{N/2} \quad \text{and} \quad b_1 < b_2 < \cdots < b_{N/2} ]

Your task is to output YES if such a partition exists and NO otherwise.

inputFormat

The first line contains an even integer \(N\), the length of the sequence. The second line contains \(N\) space-separated integers representing the sequence.

outputFormat

Output YES if the sequence can be partitioned into two strictly increasing subsequences of equal length; otherwise, output NO.

sample

4
1 3 2 4

YES