Strange Queries

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef has a set of integers A_{1}, A_{2}, ..., A_{N}. Define the Chef's number for the set as a minimal sum of penalties of the connections between numbers from this set(each number must be connected with at least one other number), if size of the set more or equal than 2, and 0 otherwise. The connection between numbers x and y has a penalty equal the absolute value xy. Chef can add elements in the set and remove elements from it, after every such operation he wants to know the Chef's number for his set. Please help him to solve this complicated task.Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two positive integers N denoting the number of elements in the set and Q denoting the number of operations performed by Chef. The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the set A, all numbers in A are pairwise distinct. Next Q lines contains two integers  type and x. type = 1 x denoting that Chef adding the number x in the set, it's guaranteed that x not in the set. type = 2 x denoting that Chef erases element x from it, it's guaranteed that x exists there.
Output
After every add/erase operation of Chef output a Chef's number for the set A.
Constraints
Should contain all the constraints on the input data that you may have. Format it like:
 1 ≤ T ≤ 1000
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ A_{i} , x ≤ 10^{9}
 1 ≤ type ≤ 2
 Sum of N over all test cases ≤ 2*10^{5}
 Sum of Q over all test cases ≤ 2*10^{5}
Subtasks
 Subtask #1: (27 points) sum of N over all test cases ≤ 5*10^{3} and sum of Q over all test cases ≤ 5*10^{3}
 Subtask #2: (24 points) sum of N over all test cases ≤ 5*10^{4} and sum of Q over all test cases ≤ 5*10^{4}
 Subtask #3: (49 points) Original constraints
Example
Input: 1 4 4 1 7 2 4 1 3 1 6 2 1 2 7 Output: 5 3 3 3.
Explanation
Example case 1. After the first operation A will be = {1, 7, 2, 4, 3} , the Chef's number for the A can be computed with next connections: 1 with 2, 2 with 3 and 7 with 4, sum of this values 12+23+74=5. After the second operation A = {1, 7, 2, 4, 3, 6}, Chef's number = 12+43+76 = 3. After the third operation A = {7, 2, 4, 3, 6}, Chef's number = 43+23+76 = 3
. Finally A = {2, 4, 3, 6} and Chef's number = 32+64=3.Author:  mgch 
Tester:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/STRQUER 
Tags  ltime54, medium, mgch, treap 
Date Added:  20112017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 