提示: 欢迎访问OurACM平台。
Problem 1674 Pop Kart

Accept: 76    Submit: 172
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

It is exciting to play the game of pop kart together.
Oaiei thinks it is too dangerous when we start at the same time.
He suggests that everyone should start the race one after another, with one minute delay.
With this rule, the player who first finishes the game will not always be the champion.
For example, if the player who started second would only finish 30 seconds after the player who started first, it means that the second player raced 30 seconds faster than the first player.
Please calculate the best rank and the worst rank one player can gain according to the final rank list.

Input

There are multiple test cases. For each test case, the first line contains an integer N(1≤N≤1000), indicating there are N players in the race and the N players are numbered from 1 to N. In the second line, there are N integers Ri(1≤i≤N) which are separated by a blank space, indicating the final rank list. The player started their race from number 1 to N. The i-th player (whose number is i) is the first Ri player finished the race.
It is guaranteed that the input is valid.

Output

For each test case, output N lines, the i-line(1≤i≤N) contains two numbers indicating the best rank and the worst rank the i-th player can gain according to the final rank list.

Sample Input

3 1 2 3 3 3 2 1 3 2 1 3

Sample Output

1 3 1 3 1 3 3 3 2 2 1 1 2 3 1 2 1 3

Source

FOJ月赛-2008年12月

Submit  Back  Status  Discuss