시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 18 2 2 11.111%

문제

N개의 우주선이 레이스를 하고 있다. i번째 우주선은 순식간에(0초에) 최대 속도인 V[i]에 도달할 수 있고, 이 속도를 레이스가 끝날 때까지 유지할 수 있다. 또한 각 우주선은 지난 대회의 결과에 따라서 X[i]라는 출발점에서 출발하게 된다. 레이스 장은 무한히 길고 X축에 평행하다. 각각의 우주선은 X축에만 평행하게 움직인다.

이렇게 레이스를 하다 보면 우주선이 다른 우주선을 추월하는 경우도 발생하게 된다. 각각의 우주선은 X[i]좌표와는 별도로 Y, Z 좌표도 가지고 있기 때문에 충돌에 대해서는 생각할 필요가 없다.

경기가 끝날 때까지 발생하는 추월들을 알아내는 프로그램을 작성하시오. 경기는 더 이상 추월이 발생하지 않을 때까지 반복된다. 우선 추월의 회수를 알아내야 하고, 연대순으로 처음 10,000개의 추월이 구체적으로 어떤 추월인지(몇 번이 몇 번을 추월하는지)를 알아내야 한다. 편의상 모든 X[i]가 다르다고 가정하자. 또한, 매 순간에 한 x좌표에는 최대 두 개의 우주선만 있을 수 있다.

입력

첫째 줄에 우주선의 개수 N(1≤N≤250,000)이 주어진다. 다음 N개의 줄에는 차례로 X[1] V[1], X[2] V[2], …, X[N] V[N]이 주어진다. 이 때 1≤X[i]≤1,000,000과 1≤V[i]≤99가 만족된다. 편의상 X[1]<X[2]<…<X[N]이 만족된다고 가정하자.

출력

첫째 줄에 추월의 회수를 1,000,000으로 나눈 나머지를 출력한다. 다음 줄들에는 각 추월에 대한 정보를 연대순으로(시간 순으로) 출력한다. 만약 추월 회수가 10,000을 넘어가면 처음의 10,000개만 출력하도록 한다. 각 줄은 두 개의 정수 i, j로 출력하는데, i번 우주선이 j번 우주선을 추월한다는 의미이다. 여러 추월이 동시에 일어나면 추월이 일어나는 위치가 출발점에 가까운(x좌표가 작은) 것을 먼저 출력한다.

예제 입력

4
0 2
2 1
3 8
6 3

예제 출력

2
3 4
1 2

힌트