조용히 완전히 영원히

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

길이가 $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$-잊힌 원소의 개수다.