#456 배열 회전과 쿼리

문제

지문 언어

다다스는 다음 쿼리를 한 번당 $O(1)$ 에 처리하는 코드를 작성했다. 여러분도 해 보자.

현재 수열을 $A=[A_1,A_2,\cdots,A_N]$ 이라 하자. 수열에 값 가 존재할 때, 를 만족하는 유일한 위치를 라 정의한다.

두 정수 $x,y$ 가 주어지는 쿼리는 다음과 같이 처리한다.

현재 수열에 $x$ 와 $y$ 가 모두 존재하며, $\operatorname{idx}(x)\leq \operatorname{idx}(y)$ 임이 보장된다.
구간 $[\operatorname{idx}(x),\operatorname{idx}(y)]$ 의 원소에 각각 을 곱한 뒤, 이 구간의 순서를 뒤집는다.

즉, 쿼리 직전의 해당 구간이

[x,\ A_{\operatorname{idx}(x)+1},\ \cdots,\ A_{\operatorname{idx}(y)-1},\ y]

였다면, 쿼리 직후에는

[-y,\ -A_{\operatorname{idx}(y)-1},\ \cdots,\ -A_{\operatorname{idx}(x)+1},\ -x]

가 된다.

초기 수열은 $[1,2,\cdots,N]$ 이다. $Q$ 개의 쿼리를 모두 처리한 뒤의 수열을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ case $_1$ case $_2$

각 테스트 케이스마다, 모든 쿼리를 처리한 뒤의 수열을 한 줄에 출력한다. 수열의 원소는 공백으로 구분한다.

#	점수	제한
1	9	$N=1$ .
2	18	모든 테스트 케이스에 대한 $N$ 의 합은 $2\,000$ 이하이다. 모든 테스트 케이스에 대한 $Q$ 의 합은 이하이다.

입력

출력

1 2 -3 4 5
-4 1 2 3

첫 번째 테스트 케이스에서 첫 쿼리 후 수열은 $[1,-4,-3,-2,5]$ 가 된다. 두 번째 쿼리 후에는 다시 $[1,2,3,4,5]$ 가 되고, 마지막 쿼리 후에는 가 된다.