완주 명단의 두 번호

문제

마라톤 대회에서 참가자 N명에게 1부터 N까지의 서로 다른 배번을 하나씩 나누어 주었다. 모든 참가자가 완주한 뒤, 운영진은 결승선을 통과한 순서대로 배번을 적은 명단을 만들었다. 이 명단에는 모든 배번이 정확히 한 번씩 등장한다. 명단의 첫 번째 배번을 가진 참가자의 순위는 1위이고, 두 번째 배번을 가진 참가자의 순위는 2위이다. 이후 참가자의 순위도 같은 방식으로 정한다. 운영진은 참가자 안내문에 넣을 비교 결과를 준비하고 있다. 비교 요청 하나에는 두 배번 X와 Y가 적혀 있다. 요청을 처리할 때는 두 배번의 참가자 중 더 먼저 결승선을 통과한 참가자의 배번과, 두 참가자의 순위 차이를 함께 적어야 한다. 순위 차이는 두 순위 중 큰 값에서 작은 값을 뺀 값이다. 예를 들어 두 참가자의 순위가 2위와 6위라면 순위 차이는 4이다. 두 사람 사이에 있는 참가자의 수를 출력하는 것이 아님에 주의한다. 한 요청에 같은 배번이 두 번 적힐 수도 있다. 이 경우에는 그 배번 자체를 먼저 출력하고, 순위 차이로 0을 출력한다. 서로 다른 참가자 사이에는 공동 순위가 없으므로, 서로 다른 두 배번이 주어진 요청에서는 먼저 완주한 참가자가 항상 하나로 결정된다. 같은 비교 요청이 여러 번 주어져도 각각 결과를 출력한다. 비교 요청은 명단을 수정하지 않는다. 모든 요청은 처음 주어진 동일한 완주 명단을 기준으로 처리하며, 앞선 요청의 결과가 뒤의 요청에 영향을 주지 않는다. 완주 명단과 Q개의 비교 요청이 주어질 때, 각 요청의 결과를 입력된 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 참가자 수 N과 비교 요청 수 Q가 공백으로 구분되어 주어진다. N과 Q는 정수이며 1 ≤ N ≤ 50,000, 1 ≤ Q ≤ 5,000이다.
둘째 줄에 완주 순서대로 N개의 배번이 공백으로 구분되어 주어진다. 이 수열은 1부터 N까지의 정수를 정확히 한 번씩 포함한다.
다음 Q개의 줄에 비교할 두 배번 X와 Y가 공백으로 구분되어 주어진다. X와 Y는 정수이며 1 ≤ X, Y ≤ N이다.

출력

각 요청에 대해 한 줄에 두 정수를 공백으로 구분하여 출력한다. 첫 번째 정수는 더 먼저 완주한 참가자의 배번이고, 두 번째 정수는 두 참가자의 순위 차이이다. X와 Y가 같으면 X와 0을 출력한다.

5 3
4 1 5 2 3
1 3
5 4
2 2

1 3
4 2
2 0

1 1
1
1 1

1 0

출처: Devin.KR 자체 제작