https://codeforces.com/contest/1506/problem/E
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 104)
• n(1 ≤ n ≤ 2 * 105)
• q1, q2, …, qn (1 ≤ qi ≤ n).

output :

• For each test case, output two lines:
  각 테스트 케이스에서 두 가지를 출력한다. 사전식으로 가장 빠른 순열 하나와 사전식으로 가장 늦는 순열 하나를 출력한다.

조건 :

• However, when Polycarp came home, he noticed that in his pocket, the permutation p had turned into an array q according to the following rule:
  qi=max(p1,p2,…,pi).
  Polycarp가 집에 도착했을 때 순열 p가 각 부분 배열의 최댓값을 저장한 배열 q로 바뀌어있었다.

---

이 작은 값을 만들어 내는 것은 훨씬 생각하기 쉬웠다. 큰 값을 만들어 내는 것이 문제였다.
맨 처음에는 그냥 현재 가지고 있는 가장 작은 값, 가장 큰 값을 저장하게 되는 것 아니냐 반복문 돌려버렸다가 넘치는 제한 범위에 시간도 넘쳐버렸다.

이걸 줄여야 하는데 작은 값은 저장하기 편했다. 가장 작은 것부터 계속 했으면 되었기 때문에 근데 생각할 것은 이미 추가한 값은 제외해야 한다는 것이다. 이 부분도 놓쳤었다.

배열

가장 큰 포인트는 배열, 큐에 저장하는 것이었다. 최대, 최소를 저장하는 아니아니 결국에는 크고 작은 것을 저장하는 것이다.
그렇다면 현재까지 가장 작은 값, 큰 값인데 이 범위를 배열로 저장해서 앞에서 부터, 뒤에서 부터 꺼내도록 하면 되는 것이다.

위치

현재 값을 저장하는 경우가 발생하는데 이것 때문에 배열에 저장을 할 때에는 이전에 저장해뒀던 숫자에서 부터 현재 - 1까지 저장을 하고 반복문에서 나와서 현재 + 1로 인덱스를 변경해준다.
물론 문장으로 쓰면 이상하니 코드에서 확인하자.
now가 1더 더해지는 걸 볼 수 있다.

그러고 나서 동일한 수가 어디까지 나오는 지 확인해서 이 위치에는 추가해 줘야 하는 수들을 배열에서 꺼내서 저장하도록 한다.

그리고 잊지 말고 출력할 때는 *을 쓰도록 하자.
배열의 값을 스페이스 바 포함해서 출력할 때는 이만한게 없다.

import sys
from collections import deque

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    ans_min, ans_max = [], []
    for_min, for_max = deque([]), []

    now, equal_num = 1, 0
    while equal_num < n:
        ans_min.append(data[equal_num])
        ans_max.append(data[equal_num])

        while now < data[equal_num]:
            for_min.append(now)
            for_max.append(now)
            now += 1
        now += 1

        idx = equal_num + 1
        while idx < n and data[equal_num] == data[idx]:
            idx += 1

        for i in range(equal_num + 1, idx):
            ans_min.append(for_min.popleft())
            ans_max.append(for_max.pop())

        equal_num = idx

    print(*ans_min)
    print(*ans_max)