Find Minimum Machines Size

You may delete some elements from the array; the remaining elements keep their relative order and at least 1 must remain. The sum of absolute differences between adjacent elements of the remaining array must equal that of the original array. Find the minimum number of elements kept (not the number deleted).

输入格式

The first line contains n; the second line contains the array. 1≤n≤200000, elements 0..10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
1 2 2 1 1

输出：

3

样例 2

输入：

3
3 3 3

输出：

1

样例 3

输入：

4
1 2 3 4

输出：

2

样例说明

Example 1: keep 1, 2, 1; the sum of adjacent differences is still 2, and at least 3 elements are needed. Example 2: the sum is 0, so keeping any 1 element is enough. Example 3: keep only 1 and 4; the total difference 3 is unchanged, so the answer is 2.