Control Points

Time Limit:1000MS  Memory Limit:65536K
Total Submit:59 Accepted:20

Description

Joe is a skilled programmer. The management of the highway police division wants to control the traffic on the highway, and hired him to solve the following problem. There are some fixed control points on the highway. The highway police division wants to place specialized devices to record information from all the control points. Such a device is very expensive and unfortunately can cover an interval of only one meter (including the left endpoint and excluding the right endpoint). The management wants to place the minimum number of devices to cover all the control points. Joe must find an efficient solution.

Input

The program input is from a text file. Each data set in the file stands for a particular configuration of control points. A data set starts with the number n (n <= 100000) – the number of control points, followed by the real values in ascending order describing the coordinates of the control points (the highway is considered a real line). The coordinates are expressed in meters.
White spaces can occur freely in the input. The input data terminate with an end of file.

Output

For each set of data the program has to print the minimum number of devices needed to cover all the control points to the standard output.
An input/output sample is in the table bellow. There are two data sets. In the first case, there are 2 points: 3.56 and 4. Only one device is needed.

Sample Input


2
3.56 4
3
1 2 2.9
Sample Output


1
2


#include<stdio.h>
const int maxn=100020;
float num[maxn];
int main()
{
    int n;
    int i,j,s;
    float k;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        for(i=1;i<=n;i++)
        {
            scanf("%f",&num[i]);
        }
        k=num[1];
        j=1;
        for(i=2;i<=n;i++)
        {
            if(num[i]>=k+1)
            {
                j++;
                k=num[i];
            }
        }
        k=num[n];
        s=1;
        for(i=n-1;i>=1;i--)
        {
            if(num[i]<=k-1)
            {
                s++;
                k=num[i];
            }
        }
        if(j>s)
        printf("%d\n",s);
        else
        printf("%d\n",j);
    }
    return 0;
}