수열과 쿼리 12

길이가 $N$인 수열 $A_1, A_2, \dots, A_N$이 주어진다. 이 수열에 다음 다섯 종류의 쿼리를 주어진 순서대로 처리하는 프로그램을 작성하시오.

• 1 l r: $l$번째 수부터 $r$번째 수까지에 나오는 서로 다른 값을 오름차순으로 정렬한 집합을 $S$라고 할 때, 아래 값을 출력한다.
• 2 x y: $A_x$를 $y$로 바꾼다.
• 3 x: $x$번째 수를 지운다.
• 4 z y: $z$번째 수의 바로 뒤에 $y$를 넣는다. $z = 0$이면 수열의 맨 앞에 $y$를 넣는다.
• 5 l r: $l$번째 수부터 $r$번째 수까지에 나오는 서로 다른 수의 개수를 출력한다.

1번 쿼리의 답은 다음과 같다.

$\left(\sum_{1 \le i < j < k \le |S|} S_i S_j S_k\right) \bmod (10^9+7)$

수열의 인덱스는 1부터 시작한다. 같은 값이 구간 안에 여러 번 나와도 $S$에는 한 번만 들어가고, $|S|$가 3보다 작으면 1번 쿼리의 답은 0이다. 수열의 크기는 항상 1 이상이다.

첫째 줄에 수열의 크기 $N$이 주어진다.

둘째 줄에 $A_1, A_2, \dots, A_N$이 주어진다.

셋째 줄에 쿼리의 개수 $M$이 주어진다.

넷째 줄부터 $M$개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

• $1 \le N, M \le 100{,}000$
• $1 \le A_i, y \le 10^9+6$
• $1 \le x \le |A|$
• $1 \le l \le r \le |A|$
• $0 \le z \le |A|$

여기서 $|A|$는 그 쿼리를 처리하기 직전의 수열의 크기다.

1번 쿼리와 5번 쿼리의 답을 주어진 순서대로 한 줄에 하나씩 출력한다.