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

input :

• t (1 ≤ t ≤ 104)
• n (1 ≤ n ≤ 5⋅105)
• b1, b2, …, bn (−109 ≤ bi ≤ 109)

output :

• For each test case, output one line containing YES if there exists an array a such that bi is the median of a1, a2, …, a2i - 1 for all i, and NO otherwise. The case of letters in YES and NO do not matter (so yEs and No will also be accepted).
  a1, a2, …, a2i - 1의 median 값이 bi인 배열로 만들 수 있다면 YES를 출력하시오. 그렇지 않다면 NO를 출력하시오.

조건 :

• The OmkArray of an array a with elements a1, a2, …, a2i - 1 is the array b with elements b1, b2, …, bkk such that bi is equal to the median of a1, a2, …, a2i - 1 for all i

a1, a2, …, a2i - 1으로 이루어진 배열 a의 OmkArray의 경우 b1, b2, …, bkk의 원소로 이루어졌는데 bi는 배열 a의 median 값이다.

---

숫자가 입력되었을 때 이 숫자를 median으로 가질 수 있는지를 확인하라는 문제이다.
어떤 두 숫자를 추가하여 새로운 중앙값을 구할 때 원래의 median에서 왼쪽으로 1칸 혹은 오른쪽으로 1칸 밖에 이동할 수 없다.

경우

현재 중앙값보다 큰 두개의 값/
오른쪽으로 1칸 이동

작은 두개의 값
왼쪽으로 1칸 이동

한개 한개 추가
그대로 유지.

불가능

현재 오른쪽에 가지고 있는 값보다 큰 값이 들어온다면 2칸 이상 움직여야 하기 때문에 불가능 한 경우이다. 이 반대로의 경우도 존재한다.

구현

현재의 중앙값에 대해 왼, 오른쪽에서 가장 큰, 가장 작은 값에 대한 비교를 지속적으로 수행한다.

새로운 값을 계속 중앙값으로 따지기 때문에 이를 업데이트 해야 한다.
가장 왼쪽에 존재하는 놈들은 음수도 포함하기 때문에 힙으로 해서 -를 붙여서 이 최댓값을 계속 기록한다.

그리고 새로운 값이 들어왔을 때 이전 중앙값과 비교해야 동일한 경우에는 따지지 않아도 되기 때문에 continue하고 그 외의 경우 배열에 저장되어 있는 값과 비교하여 판단한다.

동일한 값이 존재한다면 pop해줘야 한다. 이를 통해 새로운 중앙값을 업데이트하기 때문에 동일한 값이 존재하면 이동하는 과정에서 판단이 어려워 진다.

이전에 존재했던 중앙값은 새로 들어오는 중앙값에 따라 다르게 왼쪽, 오른쪽으로 나눠서 넣어준다.

import sys
from heapq import heappop, heappush

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))

    flag = 0
    left, right = [], []
    median = data[0]

    for i in range(1, n):
        if median == data[i]:
            continue
        elif median > data[i]:
            if left and -left[0] > data[i]:
                flag = 1
                break

            if left and -left[0] == data[i]:
                heappop(left)

            heappush(right, median)
        else:
            if right and right[0] < data[i]:
                flag = 1
                break

            if right and right[0] == data[i]:
                heappop(right)

            heappush(left, -median)

        median = data[i]

    print("NO" if flag == 1 else "YES")