EPTT - Easy Programming Tutorials

The ACM-ICPC movement has become very strong in the Dominican Republic and many students are now looking for specialized programming classes to tackle their specific needs. You work at a top school that has produced many world-class programmers. These programmers have a lot of time to spare and would like to tutor as many students as possible so as to continue producing more world-class programmers. Nonetheless, you have a very limited budget and thus want to minimize costs.

Every day you receive a number of requests from students where each request Ri has a start time Si. Each tutorial lesson lasts exactly 30 minutes. Luckily, you always have more tutors than requests. On any day, however, tutors are constrained to work only one stretch of at most two hours and each can only service one request at a time. For example, if there is a request coming in at time 0 and another one coming in at time 31, you would need two tutors to service both. If instead the second one comes at time 30, you would then need only one tutor.

Given a list of requests for a day, compute the minimum number of tutors necessary to serve them all.

Input

The first line contains a single integer R (1 <= R <= 1,000,000), the number of requests for the day. Then there are R lines. Each line contains the i-th request. Each request is represented by its integer start time in the range [0, 1410]. Thus the input has in total 1 + R lines.

Output

The output is a single integer representing the minimum number of tutors needed to serve all requests for the day.

Sample

Input:
5
0
0
30
60
61

Output:
3

Added by:kojak_
Date:2012-12-15
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:OPPAI Practice Problems

hide comments
2012-12-19 06:17:20 Govind Lahoti
a very simple problem.
easy way to score points.
:)
2012-12-18 13:36:03 kojak_
@yuvanesh: 2.
A tutor can only work a contiguous stretch of no more than 2 hours. For 0 30 90, one can serve the first two and then another one can take care of the last one.
2012-12-18 07:58:14 abcde
what in the case if the requests are
0 30 90 ??
we need 2 tutors?? or 1??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.