Zharaskhan has a permutation that consist of n distinct integers, where 0 ≤ ai < 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.

Input

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

Output

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

Example

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.