序列

题目描述 给一个数组𝑎𝑎1 , 𝑎𝑎2 , … , 𝑎𝑎𝑛𝑛 ，你希望固定尽量少的元素，满足对于剩下未固定的元素 𝑎𝑎𝑥𝑥 ，它左右都有固定的元素。令𝑎𝑎𝑙𝑙 , 𝑎𝑎𝑟𝑟 是左右两边最靠近它的固定的元素，能满足 𝑎𝑎𝑙𝑙 ≤ 𝑎𝑎𝑥𝑥 ≤ 𝑎𝑎𝑟𝑟 或𝑎𝑎𝑙𝑙 ≥ 𝑎𝑎𝑥𝑥 ≥ 𝑎𝑎𝑟𝑟 。

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

输入格式 第一行一个整数𝑛𝑛。接下来一行共𝑛𝑛个整数𝑎𝑎1 , 𝑎𝑎2 , … , 𝑎𝑎𝑛𝑛 ，保证数字两两不同。

输出格式 输出一个数，表示答案。

样例输入 1 7 1 2 3 10 5 6 4

样例输出 1 3

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

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点1,2满足𝑛𝑛 ≤ 20。

测试点3,4,5满足𝑛𝑛 ≤ 1000。

对于所有数据，满足0 ≤ 𝑛𝑛 ≤ 105 , 1 ≤ 𝑎𝑎𝑖𝑖 ≤ 109 。