该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P1677 [USACO18FEB] Hoofball B

题目描述

数轴上有 $N$ 个点，第i个点的位置为 $x_i$， $x_i$ 互不相同。

当给某个点染色后，该点不但自身颜色改变，还会把颜色传给离它最近的点，依次把颜色传下去。若距离它最近的点有两个，则把颜色传给左边的点。

求至少给多少个点染色，才能使得所有点都被染色。

输入格式

第一行一个整数 $N \ (1 \le N \le 100)$。

下来 $N$ 个整数 $x_i \ (1\le x_i\le 1000)$。

输出格式

一行一个整数，即至少给多少个点染色。

输入输出样例 #1

输入 #1

5
7 1 3 11 4

输出 #1

2

样例1 说明/提示

给点 $x=1$ 和 点 $x=11$ 染色。点 $x=1$ 传给点 $x=3$ ，在此之 后点 $x=3$ 和 点 $x=4$ 之间来回传。

点 $x=11$ 传给点 $x=7$ ，然后会传给点 $x=4$ 。

输入输出样例 #2

输入 #2

7
7 1 3 11 4 15 16

输出 #2

3