You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

校运动会开始了，小 Z 作为学校篮球队教练，准备在运动会前训练他的校队队员。

现在有 $1,2,\dots,n$ 共 $n$ 名队员排成一条直线，第 $i$ 个人在 $x_i$ 位置（可以想象成一个数轴上有 $n$ 个点，每个点的位置为 $x_i$），其中每个人都在不同的位置上。

现在，小 Z 准备让这些队员进行传球训练，初始时，这些队员手上没有球，他会把球传给若干个队员，然后这些队员会把球传给离他们最近的人。

• 具体来讲，编号为 $i$ 的队员在接到球的时候，会把球传给离他最近的队员，如果有多个队员离他的距离相同且最近，那么他就会传给 $x$ 最小（最左边）的队员。

• 注意：$i$ 号队员接到球的时候，无论是来自小 Z 的还是其他队员的，他都一定要把球再传出去。

为了保证训练效果，每个队员都必须要拿到球至少一次，请你帮助小 Z 确定最少需要准备几个球才能达到这个效果。换句话说，小 Z 在最开始的时候最少需要给几个队员准备球。

输入格式

第一行输入一个正整数 $n$ 表示队员数量。

第二行输入 $n$ 个正整数，$x_1,x_2,\dots,x_n$ 表示这 $n$ 个队员的初始位置。

输出格式

输出一个正整数 $n$ 表示小 Z 在最开始最少需要给几个队员球，才可以使得每个队员至少接到一次球。

样例 #1

样例输入 #1

5
7 1 3 11 4

样例输出 #1

2

提示

【样例解释】

小 Z 在最开始会给 $2$ 号以及 $4$ 号球，也就是 $x=1,x=11$ 的人会拿到球。

• $x=1$ 的人会把他的球传给 $x=3$ 的人，然后这个球会在 $x=3$ 的人和 $x=4$ 的人之间来回传递。

• $x=11$ 的人会把他的球传给 $x=7$ 的人，然后球会被传给 $x=4$ 的人，然后这个球又会在位于 $x=3$ 的人和位于 $x=4$ 的人之间来回传递。

• 保证了所有人都接到球至少一次，并且通过枚举可以证明，这是初始球数最少的方案。

【数据范围】

$1\le n \le 100, 1\le x_i \le 1000$，且保证每个 $x_i$ 互不相同。