{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n \"HTML-CSS\": {\n preferredFont: \"TeX\",\n availableFonts: [\"STIX\",\"TeX\"],\n linebreaks: { automatic:true },\n EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)\n },\n ShowMathMenu: false,\n TeX: {\n extensions: [\"color.js\"],\n noUndefined: {\n attributes: {\n mathcolor: \"red\",\n mathbackground: \"#FFEEEE\",\n mathsize: \"90%\"\n }\n },\n Macros: { href: \"{}\" }\n },\n tex2jax: {\n inlineMath: [[\u0027$\u0027,\u0027$\u0027], [\u0027\\\\(\u0027,\u0027\\\\)\u0027]],\n displayMath: [ [\"$$\",\"$$\"], [\"\\\\[\", \"\\\\]\"] ],\n multiline: true,\n processEscapes: true\n },\n menuSettings: {\n context: \"Browser\"\n },\n messageStyle: \"none\"\n });\n \u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\u003c/script\u003e\n\nУ Шефа есть множество целых чисел \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. Назовём \u003cstrong\u003e числом Шефа \u003c/strong\u003eмножества минимальную сумму штрафов соединений между числами из этого множества (каждое число должно быть соединено, по крайней мере, с одним другим), если размер множества хотя бы \u003cb\u003e2\u003c/b\u003e, и \u003cb\u003e0\u003c/b\u003e в противном случае. Соединение между числами \u003cb\u003ex\u003c/b\u003e и \u003cb\u003ey\u003c/b\u003e обладает штрафом, равным их абсолютной разности |\u003cb\u003ex\u003c/b\u003e-\u003cb\u003ey\u003c/b\u003e|. Шеф умеет добавлять элементы во множество и удалять их оттуда, после каждой такой операции он хочет знать число Шефа данного множества. Помогите ему решить эту сложную задачу.\n\n\u003ch3\u003eВходные данные\u003c/h3\u003e\n\u003cp\u003eВ первой строке вводится целое число \u003cb\u003eT\u003c/b\u003e, обозначающее количество тестовых случаев. Далее идёт описание каждого из \u003cb\u003eT\u003c/b\u003e случаев.\nПервая строка содержит два положительных целых числа \u003cb\u003eN\u003c/b\u003e, обозначающее количество элементов во множестве, и \u003cb\u003eQ\u003c/b\u003e, обозначающее количество операций, выполненных Шефом. Вторая строка содержит \u003cb\u003eN\u003c/b\u003e разделённых пробелом целых чисел \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, обозначающих множество \u003cb\u003eA\u003c/b\u003e, все числа в \u003cb\u003eA\u003c/b\u003e попарно различны. Следующие \u003cb\u003eQ\u003c/b\u003e строк содержат два целых числа - \u003cb\u003etype\u003c/b\u003e и \u003cb\u003ex\u003c/b\u003e. \u003cb\u003etype\u003c/b\u003e \u003d 1 \u003cb\u003ex\u003c/b\u003e обозначает, что Шеф добавляет число \u003cb\u003ex\u003c/b\u003e во множество, гарантируется, что \u003cb\u003ex\u003c/b\u003e нет во множестве. \u003cb\u003etype\u003c/b\u003e \u003d 2 \u003cb\u003ex\u003c/b\u003e обозначает, что Шеф удаляет элемент \u003cb\u003ex\u003c/b\u003e из множества, гарантируется, что \u003cb\u003ex\u003c/b\u003e лежит там.\n\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003eВыходные данные\u003c/h3\u003e\nПосле каждой операции вставки/удаления выведите число Шефа данного множества \u003cb\u003eA\u003c/b\u003e.\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003eОграничения\u003c/h3\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Сумма \u003cb\u003eN\u003c/b\u003e по всем тестам ≤ \u003cb\u003e2*10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e Сумма \u003cb\u003eQ\u003c/b\u003e по всем тестам ≤ \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\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003eПримеры\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\u003eПояснение\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003eПример 1.\u003c/b\u003e После первой операции \u003cb\u003eA\u003c/b\u003e \u003d {1, 7, 2, 4, 3} , число Шефа \u003cb\u003eA\u003c/b\u003e может быть получено следующими соединениями: \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, сумма |\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. После второй операции \u003cb\u003eA\u003c/b\u003e \u003d {1, 7, 2, 4, 3, 6}, число Шефа \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. После третьей операции \u003cb\u003eA\u003c/b\u003e \u003d {7, 2, 4, 3, 6}, число Шефа \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. В конце \u003cb\u003eA\u003c/b\u003e \u003d {2, 4, 3, 6} и число Шефа \u003d |\u003cb\u003e3\u003c/b\u003e-\u003cb\u003e2\u003c/b\u003e|+|\u003cb\u003e6\u003c/b\u003e-\u003cb\u003e4\u003c/b\u003e|\u003d3.\n\u003caside style\u003d\u0027background: #f8f8f8;padding: 10px 15px;\u0027\u003e\u003cdiv\u003e\u003c/div\u003e\u003c/aside\u003e"}}]}