给一个数组 a[1],a[2],...,a[n] ，你希望固定尽量少的元素，满足对于剩下未固定的元素 a[x] ，它左右都有固定的元素。令 a[l],a[r] 是左右两边最靠近它的固定的元素，能满足 a[l]≤a[x]≤a[r] 或 a[l]≥a[x]≥a[r] 。

输出最少的固定元素的个数。

第一行一个整数 n 。接下来一行共 n 个整数 a[1],a[2],...,a[n] ，保证数字两两不同。

输出一个数，表示答案。

7
1 2 3 10 5 6 4

3

样例解释
固定元素 1,4,7 ，那么对于 a[2],a[3] ，它们在 a[1],a[4] 之间，对于 a[5],a[6] ，它们在 a[4],a[7] 之间。

数据规模
共 10 个测试点。
测试点1,2满足 n≤20 。
测试点3,4,5满足 n≤1000 。
对于所有数据，满足 0≤n≤10^5, 1≤a[i]≤10^9 。