Sequence and queries 12

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$. Write a program that processes the following five kinds of queries in the order they are given.

• 1 l r: let $S$ be the set of distinct values that appear from the $l$-th number to the $r$-th number, sorted in increasing order, and print the value shown below.
• 2 x y: change $A_x$ to $y$.
• 3 x: delete the $x$-th number.
• 4 z y: insert $y$ right after the $z$-th number. If $z = 0$, insert $y$ at the front of the sequence.
• 5 l r: print how many distinct numbers appear from the $l$-th number to the $r$-th number.

The answer to a query of type 1 is

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

Indices of the sequence start at 1. A value that appears several times inside the range belongs to $S$ only once, and the answer to a query of type 1 is 0 when $|S|$ is smaller than 3. The size of the sequence is always at least 1.

The first line contains the size of the sequence, $N$.

The second line contains $A_1, A_2, \dots, A_N$.

The third line contains the number of queries, $M$.

Each of the next $M$ lines contains one query.

• $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|$

Here $|A|$ is the size of the sequence right before that query is processed.

For every query of type 1 and every query of type 5, print the answer on its own line, in the order the queries are given.