끊임없는 정렬과 창조함으로

끊임없는 정렬과 창조함으로

우리는 이루리 한국의 미래

이곳에서 이루리 우리의 꿈을

한국디지털미디어고등학교

- 한국디지털미디어고등학교 교가 中 -

디미고에는 끊임없이 정렬과 창조를 하면 한국의 미래를 이룰 수 있다는 전설이 있다. 하지만 정렬과 창조를 너무 많이 하면 공간도 부족하고, 무엇보다 힘들기 때문에 디미고에서는 다음과 같은 정렬과 창조 쿼리를 배열 $S$에 $Q$번만 할 수 있도록 허용하고 있다. 배열 $S$는 처음에 빈 배열이다.

• 1 x: $S$를 $x$가 $1$인 경우 오름차순, $2$인 경우 내림차순으로 정렬한다. (x \in \left\\{1, 2 \right\\}) 
• 2 x t: $S\_x$와 $S\_{x+1}$ 사이에 $t$를 삽입한다. $x = 0$인 경우에는 배열의 맨 앞에, $x = 0$이 아니면서 $x = |S|$인 경우에는 배열의 맨 뒤에 $t$를 삽입한다. 단, $|S|$는 배열 $S$의 크기를 나타낸다. $(0\leq x\leq |S|; -10^9\leq t\leq 10^9)$

$Q$개의 쿼리를 모두 수행한 뒤 만들어지는 배열을 구하는 프로그램을 작성하시오.

첫 번째 줄에 쿼리의 개수 $Q$가 주어진다. $(1\leq Q\leq 3\\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

첫 번째 줄에 모든 쿼리를 순서대로 수행한 후 $|S|$를 출력한다.

두 번째 줄에 배열 $S$의 원소를 순서대로 공백으로 구분하여 출력한다. 빈 배열일 경우 출력하지 않는다.

원래 교가의 가사는 "끊임없는 정열과 창조함으로"이다. 헷갈리지 않게 주의하자.