## The Race

## The RaceDuring the Annual Interstellar Competition for Tuned Spaceships, N spaceships
will be competing. Each spaceship i is tuned in such a way that it can
accelerate in zero time to its maximum speed V The race course is infinitely long. Because of the high speeds of the spaceships, the race course goes straight all the time. On that straight course, spaceships can pass one another very easily, without interfering with each other. Many people in the audience have not realized yet that the outcome of the race can be determined in advance. It is your task to show this to them, by telling them how many times spaceships will pass one another, and by predicting the first 10 000 times that spaceships pass in chronological order. You may assume that each spaceship starts at a different position. Furthermore, there will never be more than two spaceships at the same position of the course at any time.
## InputThe first line of the input file ## OutputThe first line of the output file Each of the subsequent lines should represent one passing, in chronological order. If there would be more than 10 000 passings, only output the first 10 000 passings. If there are less than 10 000 passings, output all passings. Each line should consist of two integers i and j, specifying that spaceship i passes spaceship j. If multiple passings occur at the same time, they have to be sorted by their position on the course. This means that passings taking place closer to the starting line must be listed first. The time of a passing is the time when the two spaceships are at the same position. ## RemarksIf you give the correct number of passings, you will earn 40% of the score per test case. For correctly giving the first 10 000 passings, you will earn the remaining 60% of the score. Each part is graded separately given that the program terminates normally within the time limit. ## Sample Input4 0 2 2 1 3 8 6 3 ## Sample Output2 3 4 1 2 ## Time limit:8 seconds per input file SubmitStatistics |