{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/LTIME54/mandarin/STRQUER.pdf\"\u003eMandarin chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/LTIME54/russian/STRQUER.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/LTIME54/vietnamese/STRQUER.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\nChef has a set of integers \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ..., \u003cb\u003eA\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e. Define the Chef\u0027s 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 \u003cb\u003e2\u003c/b\u003e, and \u003cb\u003e0\u003c/b\u003e otherwise. The connection between numbers \u003cb\u003ex\u003c/b\u003e and \u003cb\u003ey\u003c/b\u003e has a penalty equal the absolute value |\u003cb\u003ex\u003c/b\u003e-\u003cb\u003ey\u003c/b\u003e|. Chef can add elements in the set and remove elements from it, after every such operation he wants to know the Chef\u0027s number for his set. Please help him to solve this complicated task.\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe first line of the input contains an integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\nThe first line of each test case contains two positive integers \u003cb\u003eN\u003c/b\u003e denoting the number of elements in the set and \u003cb\u003eQ\u003c/b\u003e denoting the number of operations performed by Chef. The second line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ..., \u003cb\u003eA\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e denoting the set \u003cb\u003eA\u003c/b\u003e, all numbers in \u003cb\u003eA\u003c/b\u003e are pairwise distinct. Next \u003cb\u003eQ\u003c/b\u003e lines contains two integers - \u003cb\u003etype\u003c/b\u003e and \u003cb\u003ex\u003c/b\u003e. \u003cb\u003etype\u003c/b\u003e \u003d 1 \u003cb\u003ex\u003c/b\u003e denoting that Chef adding the number \u003cb\u003ex\u003c/b\u003e in the set, it\u0027s guaranteed that \u003cb\u003ex\u003c/b\u003e not in the set. \u003cb\u003etype\u003c/b\u003e \u003d 2 \u003cb\u003ex\u003c/b\u003e denoting that Chef erases element \u003cb\u003ex\u003c/b\u003e from it, it\u0027s guaranteed that \u003cb\u003ex\u003c/b\u003e exists there.\n\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\nAfter every add/erase operation of Chef output a Chef\u0027s number for the set \u003cb\u003eA\u003c/b\u003e.\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cp\u003eShould contain all the constraints on the input data that you may have. Format it like:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e1000\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eQ\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e \u003c/b\u003e, \u003cb\u003ex\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003etype\u003c/b\u003e ≤ \u003cb\u003e2\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e Sum of \u003cb\u003eN\u003c/b\u003e over all test cases ≤ \u003cb\u003e2*10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e Sum of \u003cb\u003eQ\u003c/b\u003e over all test cases ≤ \u003cb\u003e2*10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eSubtasks\u003c/h3\u003e\n\u003cul\u003e\n \u003cli\u003e\u003cb\u003eSubtask #1: (27 points) \u003c/b\u003e sum of \u003cb\u003eN\u003c/b\u003e over all test cases ≤ \u003cb\u003e5*10\u003csup\u003e3\u003c/sup\u003e\u003c/b\u003e and sum of \u003cb\u003eQ\u003c/b\u003e over all test cases ≤ \u003cb\u003e5*10\u003csup\u003e3\u003c/sup\u003e\u003c/b\u003e \u003c/li\u003e\n \u003cli\u003e\u003cb\u003eSubtask #2: (24 points) \u003c/b\u003e \u003c/b\u003e sum of \u003cb\u003eN\u003c/b\u003e over all test cases ≤ \u003cb\u003e5*10\u003csup\u003e4\u003c/sup\u003e\u003c/b\u003e and sum of \u003cb\u003eQ\u003c/b\u003e over all test cases ≤ \u003cb\u003e5*10\u003csup\u003e4\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n \u003cli\u003e\u003cb\u003eSubtask #3: (49 points) \u003c/b\u003e Original constraints\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n1\n4 4\n1 7 2 4\n1 3\n1 6\n2 1\n2 7\n\n\u003cb\u003eOutput:\u003c/b\u003e\n5\n3\n3\n3.\n\u003c/pre\u003e\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003eExample case 1.\u003c/b\u003e After the first operation \u003cb\u003eA\u003c/b\u003e will be \u003d {1, 7, 2, 4, 3} , the Chef\u0027s number for the \u003cb\u003eA\u003c/b\u003e can be computed with next connections: \u003cb\u003e1\u003c/b\u003e with \u003cb\u003e2\u003c/b\u003e, \u003cb\u003e2\u003c/b\u003e with \u003cb\u003e3\u003c/b\u003e and \u003cb\u003e7\u003c/b\u003e with \u003cb\u003e4\u003c/b\u003e, sum of this values |\u003cb\u003e1\u003c/b\u003e-\u003cb\u003e2\u003c/b\u003e|+|\u003cb\u003e2\u003c/b\u003e-\u003cb\u003e3\u003c/b\u003e|+|\u003cb\u003e7\u003c/b\u003e-\u003cb\u003e4\u003c/b\u003e|\u003d\u003cb\u003e5\u003c/b\u003e. After the second operation \u003cb\u003eA\u003c/b\u003e \u003d {1, 7, 2, 4, 3, 6}, Chef\u0027s number \u003d |\u003cb\u003e1\u003c/b\u003e-\u003cb\u003e2\u003c/b\u003e|+|\u003cb\u003e4\u003c/b\u003e-\u003cb\u003e3\u003c/b\u003e|+|\u003cb\u003e7\u003c/b\u003e-\u003cb\u003e6\u003c/b\u003e| \u003d 3. After the third operation \u003cb\u003eA\u003c/b\u003e \u003d {7, 2, 4, 3, 6}, Chef\u0027s number \u003d |\u003cb\u003e4\u003c/b\u003e-\u003cb\u003e3\u003c/b\u003e|+|\u003cb\u003e2\u003c/b\u003e-\u003cb\u003e3\u003c/b\u003e|+|\u003cb\u003e7\u003c/b\u003e-\u003cb\u003e6\u003c/b\u003e| \u003d 3\u003c/p\u003e. Finally \u003cb\u003eA\u003c/b\u003e \u003d {2, 4, 3, 6} and Chef\u0027s number \u003d |\u003cb\u003e3\u003c/b\u003e-\u003cb\u003e2\u003c/b\u003e|+|\u003cb\u003e6\u003c/b\u003e-\u003cb\u003e4\u003c/b\u003e|\u003d3."}}]}