17082번 - 쿼리와 쿼리

겨울이 가고 날이 풀리자, 택희는 겨울 옷을 세탁해 보관하고, 한참 동안 입지 않았던 후드를 하나 꺼냈다. 옷을 입던 택희는 후드의 주머니 안에 무언가 들어있음을 알아차렸다. 놀랍게도, 후드의 왼쪽 주머니와 오른쪽 주머니 안에는, 정확히 M개씩의 정수가 들어 있었다.

택희는 2018 연세대학교 교내 경진대회 문제에 사용했던 수열 하나를 꺼내 깨끗이 닦았다. 수열은 N개의 정수로 이루어져 있으며, 인덱스는 1, 2, …, N으로 매겨진다. 택희는 이 수열과 주머니에서 발견한 정수들을 이용해 ‘쿼리 놀이’를 하기로 했다.

쿼리 놀이는 아래와 같이 진행된다.

• 왼쪽 주머니에서 하나의 정수를 꺼낸다. 이 값을 L이라 한다.
• 오른쪽 주머니에서 하나의 정수를 꺼낸다. 이 값을 R이라 한다.
• L ≤ R이라면 수열의 [L, R] 구간 내에서 최댓값을 찾고, 그 값을 종이에 기록한다. L > R 이라면 종이에 10⁹을 기록한다. 그 후, 사용한 L과 R은 버린다.
• 주머니가 빌 때까지 위의 작업을 반복한다.

이 놀이가 끝나고 나면, 종이에는 M개의 정수가 쓰여 있을 것이다. 택희는 이 놀이를 반복하다가, 종이에 쓰인 정수 M개 중 최댓값을 최소화한다면 얼마가 될 지 궁금해졌다. 그리고 기왕 궁금해하는 김에, 수열의 두 원소의 위치를 바꾸는 쿼리 형태로 궁금해하기로 했다. 게다가 이런 궁금증이 무려 Q번 생겨났다!

택희의 쿼리 놀이에 대한 쿼리를 효율적으로 처리해 줄 프로그램을 작성해보도록 하자.

첫째 줄에 수열의 길이 N, 왼쪽 주머니와 오른쪽 주머니에 들어 있는 정수의 개수 M, 쿼리의 개수 Q가 주어진다. (1 ≤ N, M, Q ≤ 200,000)

둘째 줄에는 공백으로 구분된 수열의 원소 a_i가 N개 주어진다. (-10⁹ ≤ a_i ≤ 10⁹)

셋째 줄에는 왼쪽 주머니에 들어 있는 정수 l_i가 M개 주어진다. (1 ≤ l_i ≤ N)

넷째 줄에는 오른쪽 주머니에 들어 있는 정수 r_i가 M개 주어진다. (1 ≤ r_i ≤ N)

다섯째 줄부터 Q+4번째 줄까지, 쿼리에 대한 정보 i j 가 주어진다. 이는 a_i와 a_j를 서로 바꾸겠다는 의미이다. (1 ≤ i, j ≤ N)

모든 쿼리는 누적된다.

Q줄에 걸쳐, 수열 변경 직후에 대해, 놀이의 결과 정수 M개 중 최댓값의 가능한 최솟값을 출력한다.