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 race.

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.