시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB142191213.793%

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 l r: S를 l번째 수부터 r번째 수까지 수로 이루어진 정렬된 집합이라고 했을 때, 다음을 출력한다. \[\left(\sum_{1 \le i < j < k \le |S|}{S_iS_jS_k}\right) \mod{10^9+7}\]
  • 2 x y: Ax = y
  • 3 x: x번째 수를 지운다
  • 4 z y: z번째 위치의 다음에 y를 추가한다. z = 0인 경우 가장 처음에 y를 추가하는 것이다.
  • 5 l r: l번째 수부터 r번째 수 중에서 서로 다른 수의 개수를 출력한다.

수열의 인덱스는 1부터 시작하며, 수열의 크기는 항상 1보다 크거나 같다.

 

입력

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

둘째 줄에는 A1, A2, ..., AN이 주어진다.

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

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

  • 1 ≤ N, M ≤ 100,000
  • 1 ≤ Ai, y ≤ 109+6
  • 1 ≤ x ≤ |A|
  • 1 ≤ l ≤ r ≤ |A|
  • 0 ≤ z ≤ |A|

출력

1번과 5번쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

5
1 2 3 2 1
8
1 1 3
5 1 5
2 2 4
1 2 4
3 3
4 0 5
1 1 2
1 1 5

예제 출력 1

6
3
24
0
78

예제 입력 2

10
5 4 3 5 4 1 5 4 3 1
15
2 8 580347
4 6 503576
1 2 5
5 8 11
1 2 6
4 7 565239
3 6
3 11
3 3
2 9 674360
1 1 6
2 2 589693
4 5 236488
1 8 9
5 2 7

예제 출력 2

60
4
107
788510349
0
6

출처