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
2013-05-24 14:05:15 Man Mohan Mishra
nice problem !!
@ abdou 00: answer is 4.
2013-05-21 11:37:09 Ashutosh Singla
got AC after using map instead of an array :P

Last edit: 2013-05-21 12:45:52
2013-04-30 02:18:18 Arika Saputro
nice :D
2013-03-13 05:05:22 tuhin
@kojak_ getting WA in 11th judge ,cannot understand for which test case it is failing my submission id is 8880868 . please let me know what is wrong
2013-01-20 19:36:45 abdou_93
Answer for this test case
16
0
30
30
60
60
60
90
90
90
90
120
120
120
150
150
180
"4 or 6"
2012-12-31 13:27:19 Animesh Sinha
@Jiten
The output is 2 as any tutor can teach for atmost 2 hrs continuously
2012-12-29 11:37:44 Nitin Khanna
@kojak_ :
For the testcase 0 30 90 you have mentioned that 2 tutors are needed.Why 2 coz if 1st tutor will start teaching at 90 he will be done by 119 which is less that 120(2 hr).

@Nitin : Yes, 2 is correct answer for
3
0
30
90


Last edit: 2012-12-29 13:56:00
2012-12-28 07:03:14 Jiten Agarwal
output for 5 0 30 60 90 120
??
2012-12-27 06:19:48 Jiten Agarwal
@Animesh ain't the output 1 for 5 0 30 60 90 120??
2012-12-25 13:21:18 :C++:
@kojak_ why i m getting wa...
run on many test cases....
submission id 8342587...
pls help

Last edit: 2012-12-25 13:23:52
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.