A new road has been opened. It is **L** meters long, and it is divided
into one-meter sections called positions. There are traffic lights at various
positions on the road. If there's a traffic light at position *i*, it means that a
car at position *i* must wait until the light is green before
it can proceed to position *i+1*. Traffic lights are either red or green,
and they change every five seconds.
There are some cars waiting to enter into the road. Each car is one
meter long, and there can never be more than one car at a single position of the road.
Once a car enters the road it cannot overtake other cars. The cars' speeds are given
in the int[] **speeds**, where the i-th element is the speed of the i-th car.
Each traffic light starts out red, but the duration of that first red light varies between
one and five seconds, inclusive. Then, the five second cycle starts. The initial red light
duration may be different for each traffic light.
Suppose that the road goes from left to right. The cars move as follows:
- Step 1: Each car already in the road (from right to left) tries to move rightward as many positions as its speed indicates, but it can be blocked by another car or a red traffic light (here rightward means increasing its position).
Then, if position 0 of the road is free, the car with the lowest index in **speeds** that has not yet entered the road enters at position 0, without moving.
This step takes one second.
- Step 2: The traffic lights are updated, if necessary. This step takes no time.
- Step 3: If all the cars have left the road, stop, otherwise go to Step 1.
You are given **L**, the road length, **speeds**, the speed of each car, and **lights**, the position of each traffic light.
Determine the duration of the first red light for each traffic light that
minimizes the total time it takes for all the cars to leave the road (that is, the number of seconds elapsed until the last car leaves the road). Return a int[], where the i-th element is
the duration of the first red light of the i-th traffic light. If two solutions give the same time, return the one that
comes first lexicographically. |