Alimzhan’s Triplets

Zharaskhan has a permutation that consist of n distinct integers, where 0ai < n. But as he dislikes his friend Alimzhan, he wants to transform his array by deleting a minimum number of elements from his array so long there is no Alimzhan’s Triplets in it.

What is Alimzhan’s Triplet, you may wonder.Well, Alimzhan describes it as any three consecutive elements in the array that are either ascending or descending, i.e. ai < ai+1 < ai+2 or ai > ai+1 > ai+2 for some i.

Zharaskhan is very busy making money for Mark over at Facebook, so he asked you, the participant of this very KBTU Open, to find the answer.


The first line contains a single integer n (1n2 * 105). The next line contains n integers describing the array ai (0ai < n) and all elements are distinct, which is Zharaskhan’s array.


Output a single number – the minimum number of elements required to remove from Zharaskhan’s array to make it free of Alimzhan’s Triplets.


In the first sample test, there is only a single Alimzhan’s Triplet: [0, 2, 3]. Thus, deleting any of these 3 elements is enough.

Time limit 1 second
Memory limit 128 MiB
Input example #1
0 2 3 1
Output example #1
Input example #2
0 2 1 4 3
Output example #2
Input example #3
3 0 5 2 1 4
Output example #3
Source 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem G