A sequence \(b_1, b_2, \dots, b_m\) of length \(m\) is called wonderful if its two edge elements are strictly greater than every one of the other \(m-2\) elements. In other words, \(\min(b_1, b_m) > \max(b_2, b_3, \dots, b_{m-1})\) must hold. Note that if \(m \le 2\), the sequence is always wonderful.
You are given an array \(a\) of length \(n\). Your task is to split the array into several intervals so that every element belongs to exactly one interval and the elements of each interval form a wonderful sequence. Find the minimum number of intervals needed.
The first line contains \(n\) (\(1 \le n \le 200\,000\)).
The second line contains \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).
Print a single number – the minimum number of intervals.
9 4 1 5 3 9 5 7 8 9
3
3 2 2 2
2
3 3 1 2
1
In the first example, the array can be split as \([4, 1, 5], [3], [9, 5, 7, 8, 9]\).
In the second example, it can be split as \([2, 2], [2]\).
In the third example, the whole array is wonderful, so the minimum answer is 1.