rektprob

N robots take part in the marathon. Robots must overcome the same distance by moving along tracks one meter wide each.
It is known that the robot located on the i-th track overcomes the distance in ai seconds.
At the starting point of each robot, a special signaling device is installed, which should be activated at the time of launch. To make the competition less predictable, judges in front of
Start can disable some signaling devices, other devices will remain active. Only active devices are triggered at the moment when the main judge starts
marathon. At the beginning of the marathon, at least one signaling device must be active.
Each robot starts moving at the moment when it reaches the starting signal from
active device. The signal propagates at a speed of 1 meter per second. Distance between
paths i and j is equal to | i - j | meters Denote as xi the distance from the i-th track to the nearest
tracks containing the active device. The robot on the i-th track will start moving in xi seconds
after the start, overcome the distance in ai seconds, and finish in fi = ai + xi seconds after
start marathon.
Let ki be the number of robots that finished strictly before the i-th robot. I-th place
the robot at the end of the marathon is ki + 1. If several robots finish at the same time,
and before them k robots finished, it is considered that they all took (k + 1) -th place.
Consider an example. Let n = 3, robots overcome the distance for a1 = 2, a2 ​​= 3 and a3 = 5
seconds, and only the signal device of the third robot was active. Then the first robot
will start moving 2 seconds after the start of the race, f1 = 4. The second robot will start moving
in 1 second, f2 = 4. The third robot will start moving at the moment of start, f3 = 5. By the end of the race
The first and second robots share the first place, the third robot takes the third place. If, for example,
all three signaling devices will work, robots finish in f1 = 2, f2 = 3, f3 = 5, seconds,
respectively. The first robot will take the first place, the second robot will take the second place, and the third
robot - the third place.
As you can see from the example, the place that the robot will take depends on which signaling devices are active. It is necessary to process two types of requests:
1) for each robot to determine the minimum place that it can take;
2) for each robot to determine the maximum place that it can take.
It is required to write a program that, by the type of request and information about the time of passage
distance by each robot determines for each robot the minimum or maximum place,
which he can take in a robo marathon.