XXXXXXXX - Sum of Distinct Numbers

no tags 

You are given N numbers. You have to perform two kinds of operations:
U x y - x-th number becomes equal to y.
Q x y - calculate the sum of distinct numbers from x-th to y-th. It means that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7).

Input

The first line of input contains an integer N. 1<=N<=50000
The second line consists of N numbers.
The third line consists of an integer Q. 1<=Q<=100000
The following Q lines will consist of queries of the form described in the task description.
All numbers in input will fit in the signed 32-bit type.

Output

Output an answer for every query of the second type.

Example

Input:
5
1 2 4 2 3
3
Q 2 4
U 4 7
Q 2 4

Output:
6
13

Hint: Time limit is ~ 1.5*(my program's execution time in the worst case)


hide comments
Josip Klepec: 2016-07-01 10:14:32

odlićno

secta: 2016-04-20 11:04:16

Is O(Q*log^2(N)) enough, I keep getting TLE?

Hani Ghazi: 2016-02-06 22:35:20

why still get WA at 20 ??
can anyone give me some cases !!

Shambhavi Mishra: 2015-08-11 18:48:06

Can someone help me with this question ?

pikku: 2015-06-17 11:06:43

Replaced int with long long and still getting WA on 20th test case. Can someone help me with this?

Last edit: 2019-03-23 17:43:30
Raj Kumar: 2014-12-17 21:39:44

Can the input numbers be negative??

Rishabh Raj: 2011-11-01 05:55:02

hey like for input like 4 4 4 what will be the sum.? 4 or 0 ..?

Edit : it is 4. It is hard for problem statement to be more clear than it already is.

Last edit: 2011-11-17 20:18:06
Buda IM (retired): 2011-08-22 15:10:17

Beautiful problem.

Last edit: 2011-08-17 17:02:52
[Rampage] Blue.Mary: 2011-08-22 15:10:17

An enhanced version of problem GSS2 :P


Added by:Sergey Kulik
Date:2011-06-23
Time limit:1s
Source limit:44444B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Known problem