In preparation for the upcoming hoofball tournament, Farmer John is drilling his NN cows (conveniently numbered 1…N1…N , where 1≤N≤1001≤N≤100 ) in passing the ball. The cows are all standing along a very long line on one side of the barn, with cow ii standing xixi units away from the barn (1≤xi≤10001≤xi≤1000 ). Each cow is standing at a distinct location.

At the beginning of the drill, Farmer John will pass several balls to different cows. When cow ii receives a ball, either from Farmer John or from another cow, she will pass the ball to the cow nearest her (and if multiple cows are the same distance from her, she will pass the ball to the cow farthest to the left among these). So that all cows get at least a little bit of practice passing, Farmer John wants to make sure that every cow will hold a ball at least once. Help him figure out the minimum number of balls he needs to distribute initially to ensure this can happen, assuming he hands the balls to an appropriate initial set of cows.

Input

The first line of input contains NN . The second line contains NN space-separated integers, where the ii th integer is xixi .

Output

Please output the minimum number of balls Farmer John must initially pass to the cows, so that every cow can hold a ball at least once.

Example

Input

Copy

5
7 1 3 11 4

Output

Copy

2

Note

In the above example, Farmer John should pass a ball to the cow at x=1x=1 and pass a ball to the cow at x=11x=11 . The cow at x=1x=1 will pass her ball to the cow at x=3x=3 , after which this ball will oscillate between the cow at x=3x=3 and the cow at x=4x=4 . The cow at x=11x=11 will pass her ball to the cow at x=7x=7 , who will pass the ball to the cow at x=4x=4 , after which this ball will also cycle between the cow at x=3x=3 and the cow at x=4x=4 . In this way, all cows will be passed a ball at least once (possibly by Farmer John, possibly by another cow).

It can be seen that there is no single cow to whom Farmer John could initially pass a ball

so that every cow would eventually be passed a ball.

 

题意：n个小朋友互相传球，每个人只传给离他最近的那个人。求至少要发多少个求能使得所有的人都玩到球。

思路：设f(i,0/1):前i个人，第i个人是从左/右向右/左传对于的最少发球数。

单给第i个人发一个球的话，既可以作为左->右，也可以作为右->左

先预处理出ok[i][j]:如果球在i手上，会不会传给j

那么f[i][0]=min(f[i-1][0]+(!ok[i-1][i]),f[i-1][1]+1); f[i][1]=min(f[i-1][1]+(!ok[i][i-1]),f[i-1][0]+1);

#include<bits/stdc++.h>
using namespace std;
#define maxn 200

int n,a[maxn],f[maxn][2],ok[maxn][maxn];

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	a[0]=-(1<<25);a[n+1]=(1<<25);
	for(int i=1;i<=n;i++)
	{
		if(a[i+1]-a[i]<a[i]-a[i-1])ok[i][i+1]=1;
		else ok[i][i-1]=1;
	}
	f[1][0]=f[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		f[i][0]=min(f[i-1][0]+(!ok[i-1][i]),f[i-1][1]+1);
		f[i][1]=min(f[i-1][1]+(!ok[i][i-1]),f[i-1][0]+1);
	}
	cout<<min(f[n][0],f[n][1])<<endl;
//	for(int i=1;i<=n;i++)cout<<f[i][0]<<" "<<f[i][1]<<endl;
	return 0;
}