일본 침몰 2 timer 3초 memory 1024MB

일본 열도는 동서에 길쭉한 열도이다. 일본 열도는 남북 방향의 경계선에 따라 N 개의 구획으로 나뉘어져 있다. 구획에는 서쪽부터 순서대로 1에서 N까지의 번호가 붙여져 있다. 현재 구획 i (1≤i≤N)의 고도는 Aim입니다.

일본 열도에서는 종종 폭풍이 일어나고 있습니다. 폭풍이 일어나면 파도에 의한 침식으로 각 구획의 고도가 다음과 같이 감소한다.

힘 x의 서풍 폭풍에서는 서쪽에서 세어 x 개 이내의 구획 중, 「그보다 서쪽에 자신보다 고도가 높은 구획이 존재하지 않는다」와 같은 모든 구획의 고도가 1 m 감소한다. 즉, 폭풍 전의 구획 i의 표고를 ai로 나타내면, i≤x이고, 1≤k<i가 되는 모든 k에 대해 ak≤ai가 되는 경우에 구획 i의 표고는 1m 줄어들고, 그렇지 않으면 변하지 않습니다.

강도 x의 동풍 폭풍에서는 동쪽에서 세어 x 개 이내의 구획 중, 「그보다 동쪽에 자신보다 고도가 높은 구획이 존재하지 않는다」와 같은 모든 구획의 고도가 1 m 감소한다. 즉, 폭풍 전에 구획 i의 고도를 ai로 나타내면, i ≧ N - x + 1이고 i < k ≤ N 인 모든 k에 대해 ak ≤ ai 인 경우 구획 i의 고도는 1m 줄어들고 다른 경우에는 변하지 않습니다.

당신은 향후 Q 일의 사건을 시뮬레이션해야합니다. j 일째 (1 ≤ j ≤ Q)에는 다음과 같은 사건이 일어난다.

Tj = 1 일 때 강도 Xj의 서풍 폭풍이 발생합니다.

Tj = 2 일 때, 강도 Xj의 동풍 폭풍이 일어난다.

Tj = 3 일 때, 그 시점에서 구획 Xj의 고도를보고한다.

제약에 의해 어느 구획의 고도도 부가되지 않는 것이 보증된다.

현재 각 구획의 고도와 향후 Q 일간의 사건이 주어지므로 Tj = 3 인 날에 대해 지정된 구획의 고도를 구하는 프로그램을 작성하라.