Monotonic Subsequences Partition

You are given a sequence of N integers: \(a_1,a_2,\dots,a_N\). A subsequence \(b_1,b_2,\dots,b_L\) of the given sequence is defined by the fact that for each \(i\) (\(1\le i\le L\)) there exists an index \(j\) (\(1\le j\le N\)) such that \(b_i=a_j\), and if \(i_1<i_2\) then the corresponding indices \(j_1<j_2\) hold.

A subsequence is said to be non-decreasing if for every \(i\) (\(1\le i<L\)), \(b_i\le b_{i+1}\). It is said to be non-increasing if for every \(i\) (\(1\le i<L\)), \(b_i\ge b_{i+1}\).

The given sequence is called NICE if it is possible to partition the sequence into K disjoint subsequences (every element belongs to exactly one subsequence) such that:

1. Each subsequence has at least 2 members.
2. Each subsequence is either non-decreasing or non-increasing.

Your task is to determine the minimum possible \(K\) for which such a partition is possible. If no valid partition exists, output \(-1\).

Note: In a sequence of two elements, it is always monotonic. However, when the total number of elements is odd, you must form at least one subsequence with more than two elements and that subsequence must be monotonic.

inputFormat

The first line contains an integer \(N\) (the number of elements). The second line contains \(N\) integers \(a_1,a_2,\dots,a_N\) separated by spaces.

outputFormat

Output a single integer representing the minimum number of subsequences \(K\) needed to partition the given sequence satisfying the conditions. If no such partition exists, output \(-1\).

sample

4
1 2 3 4

1