내 집 마련하기

서강대학교에는 비어 있는 집이 $N$채 있다. 학교는 $N$명의 사람이 각자 한 채씩 입주하도록 배정하려고 한다. 학교는 입주자에게 혜택을 준다. $x$번 집에 $y$번 사람이 입주하면 $xy$만큼의 세금을 감면한다.

집의 배정 상태는 $1$부터 $N$까지의 정수를 하나씩 원소로 가지는 수열 $A_1, A_2, \dots, A_N$으로 나타낸다. 이는 $i$번 집에 $A_i$번 사람이 배정되어 있다는 뜻이다.

다음 쿼리를 해결하는 프로그램을 작성하라.

• $L$ $R$: 초기 배정 상태에서 $L$번부터 $R$번까지의 사람들은 현재 배정받은 집을 학교가 원하는 만큼 서로 교환할 수 있다. 감면되는 세금의 합이 최대가 되도록 다시 배정했을 때의 수열 $A$를 출력한다.

모든 쿼리는 독립적이다. 쿼리가 끝나면 수열 $A$는 초기 상태로 돌아간다.

첫째 줄에 수열의 길이 $N$이 주어진다. $(1 \le N \le 300)$

둘째 줄에 수열 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le N)$

셋째 줄에 쿼리의 개수 $M$이 주어진다. $(1 \le M \le 300)$

넷째 줄부터 $M$개의 줄에 걸쳐 쿼리를 나타내는 두 정수 $L$, $R$이 공백으로 구분되어 주어진다. $(1 \le L \le R \le N)$

쿼리마다 정답을 한 줄에 하나씩 출력한다.

각 줄에는 쿼리가 끝난 후의 수열 $A_1, A_2, \dots, A_N$을 공백으로 구분하여 출력한다.

가능한 답이 여러 가지라면 아무거나 하나 출력한다.