The largest sawtooth subsequence
A sequence of numbers is termed a sawtooth sequence if each element (except the first and last) is either greater than both its neighbors or less than both its neighbors. For instance, the sequence 1, 2, 1, 3, 2 qualifies as a sawtooth sequence, whereas 1, 2, 3, 1, 2 does not, because 1 < 2 < 3. Any sequence consisting of a single element is considered a sawtooth sequence. A sequence with two elements is a sawtooth sequence if the two elements are not equal.
Given a sequence, your task is to determine the minimum number of elements that must be removed to transform the sequence into a sawtooth sequence.
Input
The first line of the input contains a single integer N (1 ≤ N ≤ 100000) representing the number of elements in the sequence. The second line contains N natural numbers, each not exceeding 10000, which are the elements of the sequence.
Output
Output a single integer representing the minimum number of elements that need to be removed.