30619번 - 내 집 마련하기 스페셜 저지

서강대학교에는 비어 있는 집이 $N$채 있다. 그래서 서강대학교는 $N$명의 사람들이 한 사람당 한 채의 집에 입주해 살 수 있도록 배정해 주려고 한다. 서강대학교에서는 입주한 사람들을 위해 특별한 혜택을 제공하는데, 바로 $x$번 집에 $y$번 사람이 입주해서 살게 되면 $xy$만큼의 세금을 감면해 준다는 것이다.

사람들이 집에 배정된 상태는 $1$부터 $N$까지의 정수를 하나씩 원소로 가지는 수열 $A_1,A_2,\cdots,A_N$로 표현되는데, 이는 현재 $i$번 집에 $A_i$번 사람이 배정되어 있음을 의미한다.

다음과 같은 쿼리를 해결하는 프로그램을 작성해 보자.

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

모든 쿼리는 독립적이다. 즉, 쿼리가 실행된 직후 수열 $A$는 초기 상태로 복구된다.

첫째 줄에 수열의 길이를 나타내는 정수 $N$이 주어진다. $(1\leq N \leq 300)$

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

셋째 줄에 쿼리의 개수를 나타내는 정수 $M$이 주어진다. $(1\leq M \leq 300)$

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

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

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

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