The phone you bought a long time ago has a built-in memory that keeps track of all the calls you receive. It logs the date (month and day) and the time (hour and minute) of each call along with the caller’s number. Only a limited number of calls can be logged (memory was still expensive then).
You discover that the limit is almost reached and therefore plan to delete some entries from the log. In choosing the entries to delete you have to consider two restrictions:
- There are some (important) entries you want to keep.
- You want to be able to recover the year (which the phone does not log) of each call you keep. The recovery procedure is described below.
Calculate the minimal number of entries that must be kept to satisfy these requirements.
Recovery of years
Given a list of timestamps (consisting of month, day, hour, and minute) of calls, you find out the year of each call by the following procedure:
- The last call in the list occurred in the current year.
- You compare its timestamp t to the timestamp t' of the previous call. If t' < t, you assume that both calls occurred in the same year. If t' ≥ t, you assume that the previous call occurred the year before.
- You iterate backwards through the list and reason as in 2. at each step.
Note that this procedure is not correct in general, but you may assume that it is for the input you get, and you have to ensure that it gives the same result for the shortened log.