Now you are asked for help by the organizers of the Winter Olympic Games
2014, which, as you know, will be held in Yekaterinozavodsk. And although
there are still 5 and a half years ahead, the first sport facility is already put
into operation. It is the track for the ski race.
Although the track has modern and reliable equipment, the organizers want to know what to do in case it fails.
For instance, what will happen if the stopwatch on the finish breaks down and only the relative
order of the sportsmen is known? The rules of the ski race make things even worse: the participants
start the race one after another, with a 30 seconds delay, and therefore the sportsman who finishes first
doesn't have to be the first in the ranklist. For example, if the sportsman who started second
would finish 25 second after the sportsman who started first, it would mean that he passed the track
5 seconds faster than his rival and therefore should be placed higher in the final ranklist.
You are to write a program that will determine for each sportsman the highest and the lowest place
he can possibly have in the final ranklist, given the relative order in which the sportsmen finished
The first line contains an integer n — the number of the race participants (1 ≤ n ≤ 2000).
The participants are numbered from 1 to n according to the order they started the race.
The second line contains a permutation of numbers from 1 to n — the order in which the skiers finished.
Output n lines; i-th line should contain a pair of space-separated integers —
the lowest and the highest possible place in the final ranklist for i-th race participant.
3 5 1 4 2 6
Problem Author: Eugene Kurpilyansky, Alexey Samsonov
Problem Source: USU Junior Contest, October 2008