30512번 - 조용히 완전히 영원히

문제

세종이는 다음과 같은 문제를 풀고 있다.

길이가 $N$인 수열 $A_1,A_2,\cdots ,A_N$이 주어진다. 이때 다음과 같은 업데이트가 총 $Q$개 주어진다.

• L R x: 모든 $L\leq i\leq R$에 대해 $A_i=\min(A_i,x)$ 를 적용한다. $(1\leq L\leq R\leq N;\ 0\leq x\leq 1,000円,000円)$

$Q$개의 업데이트를 차례대로 수행한 후의 수열을 구하시오.

세종이는 어떤 업데이트 이후로 더 이상 값이 변경되지 않는 원소가 생김을 발견했다. 감성적인 세종이는 이런 원소를 잊힌 원소라고 이름 짓고 이들의 개수를 기억하기로 했다. 구체적으로, 어떤 원소가 $i$번째 업데이트를 처리한 후 남은 업데이트에 의해 값이 변경되지 않는다면 그 원소는 $i$-잊힌 원소가 된다. 임의의 두 양의 정수 $i<j$에 대해, 모든 $i$-잊힌 원소는 $j$-잊힌 원소이기도 함에 유의하라.

세종이가 구해야 하는 수열과 각 업데이트 후의 잊힌 원소의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기를 나타내는 정수 $N$이 주어진다. $(1\leq N\leq 100,000円)$

둘째 줄에 $N$개의 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. $(0\leq A_i\leq 1,円 000,円 000)$

셋째 줄에 업데이트의 수를 나타내는 정수 $Q$가 주어진다. $(1\leq Q\leq 100,000円)$

넷째 줄부터 $Q$개의 줄에 걸쳐 업데이트가 한 줄에 하나씩 처리해야 하는 순서대로 주어진다.

출력

첫째 줄에 업데이트를 모두 수행한 후의 수열을 공백으로 구분해 출력한다.

둘째 줄에 $Q$개의 정수 $D_1,D_2,\cdots ,D_Q$를 공백으로 구분해 출력한다. 이때 $D_i$는 $i$-잊힌 원소의 개수다.

제한

힌트