플롭 정렬

CCO에 기여하고 싶은 마음에, Robert는 세그먼트 트리 문제를 하나 만들어 보기로 했다. 그 문제의 명세는 다음과 같다.

1과 N 사이의 서로 다른 정수 N개가 주어진다. 이들은 한 줄로 나열되어 있으며, 왼쪽에서 i번째 정수는 ai이다 (1 ≤ i ≤ N). 어떤 원소 집합에 대한 플롭 연산이란, 그 집합의 최솟값과 최댓값을 서로 교환하는 것이다. Q개의 플롭 연산이 주어지며, 각 연산은 두 수 l과 r을 지정한다 (1 ≤ l ≤ r ≤ N). 각 연산마다 구간 [l, r] (즉, al, al+1, . . . , ar−1, ar로 이루어진 부분)에 플롭을 수행해야 한다. 주어진 순서대로 Q개의 플롭을 모두 수행한 뒤, 최종 결과를 보고해야 한다.

문제 지문을 다 쓴 Robert는 이제 테스트 데이터를 만들어야 한다. 특정 테스트 케이스 하나에서는, 초기 수열과 최종 수열에 어떤 내부 농담을 숨기려고 한다. 이 두 수열이 고정되어 있을 때, 첫 번째 수열을 두 번째 수열로 바꾸는 플롭 연산의 나열을 아무거나 하나 찾아 도와주자.

첫째 줄에는 정수 N이 주어진다 (1 ≤ N ≤ 4096). 둘째 줄에는 1과 N 사이의 서로 다른 정수 N개가 공백으로 구분되어 주어지며, 초기 수열을 나타낸다. 셋째 줄에도 1과 N 사이의 서로 다른 정수 N개가 공백으로 구분되어 주어지며, 최종 수열을 나타낸다.

출력의 첫째 줄에는 정수 Q를 출력한다 (Q ≤ 300 000). 다음 Q개 줄에는 1 ≤ l ≤ r ≤ N인 두 정수 l과 r을 출력한다.