Задача A. Разность квадратов ≡

Условие

Вы участвуете в разработке программного модуля для системы символьных вычислений. Модуль будет использоваться для решения специального вида диофантовых уравнений.

По заданному целому неотрицательному целому числу n разрабатываемый модуль должен найти два натуральных числа x и y, для которых выполнено равенство x² − y² = n. Найденные числа не должны превышать 2⁶² − 1.

Требуется написать программу, которая по заданному целому неотрицательному числу n находит натуральные числа x и y, не превышающие 2⁶² − 1, разность квадратов которых равна n.

Формат входных данных

В единственной строке дано одно целое число n (0 ≤ n ≤ 2⁶⁰). Обратите внимание, что заданное во вводе число не помещается в 32-битный тип данных, необходимо использовать 64-битный тип данных (например, long long в C++, int64 в Паскале, long в Java).

Формат выходных данных

Если искомые x и y существуют, то необходимо вывести две строки: в первой строке выведите слово Yes, а во второй  — искомые x и y.

Если подходящих пар x и y несколько, можно вывести любую из них, но должно выполняться условие 1 ≤ x, y ≤ 2⁶² − 1.

Если решения нет, в единственной строке необходимо вывести слово No.

Ограничения

0 ≤ n ≤ 2⁶⁰

1 ≤ x, y ≤ 2⁶² − 1

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

3

Yes
2 1

2

No

Задача B. Превышение скорости ≡

Условие

Превышение скорости является опасным нарушением, значительно увеличивающим вероятность трагических последствий транспортных происшествий. К сожалению контроль скорости с использованием радаров и камер не решает проблему полностью. Притормаживая перед камерами, водители едут со значительным превышением на участках дорог, где контроль не ведётся. С целью предотвращения такого поведения используется назначение штрафа за гарантирование превышение скорости, основанное на времени проезда дороги.

Рассмотрим дорогу, состоящую из n участков, пронумерованных от 1 до n. Длина i-го участка составляет l_i метров. На i-м из участков установлено ограничение по скорости в v_i м/с.

За превышение скорости предусмотрены штрафы. В зависимости от превышения, установлены различные штрафы, величина штрафа вычисляется следующим образом.

Пусть e — максимальное превышение разрешённой скорости в процессе пребывания автомобиля на всей дороге, то есть максимальная разница между скоростью автомобиля и максимальной разрешенной скоростью на участке, где он в этот момент находится. Если превышения скорости не было, то штраф не взимается. В противном случае штраф вычисляется так:

• если 0 < e ≤ a₁, то штраф составляет f₁ денежных единиц
• если a₁ < e ≤ a₂, то штраф составляет f₂ денежных единиц
• …
• если a_m − 2 < e ≤ a_m − 1, то штраф составляет f_m − 1 денежных единиц
• если a_m − 1 < e, то штраф составляет f_m денежных единиц

Таким образом, есть m диапазонов превышения скорости и соответствующие им штрафы.

Автоматическая система назначения штрафов получила данные о q автомобилях. Для удобства пронумеруем их от 1 до q. Известно, что i-й автомобиль заехал на дорогу в момент времени s_i, проехал все n участков, после чего выехал с нее в момент времени t_i. Отсчёт времени будем вести в секундах с открытия дороги.

Для каждого из автомобилей система должна определить, какой максимальный штраф можно гарантированно выписать этому автомобилю, основываясь только на времени заезда на дорогу и выезда с нее.

Требуется написать программу, которая по описанию границ диапазонов превышения скорости, соответствующих штрафов и временам въезда/выезда автомобилей определяет для каждого автомобиля максимальный штраф, который можно выписать этому автомобилю.

Формат входных данных

Первая строка входных данных содержит единственное целое число n — количество участков на дороге.

Вторая строка содержит n целых чисел v_i — ограничения скорости на участках.

Третья строка содержит n целых чисел l_i — длины участков.

Четвертая строка содержит единственное целое число m — количество границ диапазонов превышения скорости.

Пятая строка содержит m − 1 целых чисел a_i — границы диапазонов превышения скорости. Гарантируется, что значения a_i строго возрастают. Обратите внимание, что если m = 1, то пятая строка ввода пустая.

Шестая строка содержит m целых чисел f_i — штрафы за диапазоны превышения скоростей. Гарантируется, что значения f_i возрастают.

Седьмая строка содержит единственное целое число q — количество автомобилей, которые надо обработать.

Каждая из следующих q строк содержит два целых числа s_i и t_i — время заезда на трассу и выезда с неё i-го из рассматриваемых автомобилей .

Формат выходных данных

Для каждого из q автомобилей выведите в отдельной строке максимальный штраф, который гарантированно можно выписать этому автомобилю, основываясь только на временах его заезда на дорогу и выезда с нее. Если возможна ситуация, что автомобиль ни разу не превысил разрешённую скорость, следует вывести 0.

Гарантируется, что если время въезда или выезда автомобиля изменить не более чем на 10^− 5, штраф, который можно ему выписать, не изменится.

Ограничения

1 ≤ n ≤ 10

1 ≤ v_i, l_i, a_i, f_i ≤ 10⁹

1 ≤ m, q ≤ 10⁵

1 ≤ s_i < t_i ≤ 10⁹

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

3
10 20 30
400 500 600
6
1 5 10 12 16
100 300 600 800 1000 1500
3
10 100
20 70
45 100

0
800
600

Задача C. Борьба с рутиной ≡

Условие

Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.

Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом a_i.

Для оценки рутинности работы сотрудника будем использовать следующую характеристику. Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как S_d и будем называть её d-разнообразием. Чем d-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений [S₁, S₂, …, S_n].

Требуется написать программу, которая по заданной последовательности a₁, a₂, …, a_n типов выполняемых сотрудником заданий вычисляет его профиль вариативности.

Формат входных данных

В первой строке находится единственное целое число n  — количество последовательных рабочих дней, которые необходимо проанализировать (1 ≤ n ≤ 2 ⋅ 10⁵).

Во второй строке находится n целых чисел a₁, a₂, …, a_n  — типы заданий, которое выполнял сотрудник (1 ≤ a_i ≤ 10⁹).

Формат выходных данных

Выведите n целых чисел: S₁, S₂, …, S_n.

Ограничения

1 ≤ a_i ≤ 10⁹

1 ≤ n ≤ 2 ⋅ 10⁵

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Замечание

Рассмотрим, как вычисляются значения S_d в первом примере.

1-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из одного дня.

Значение 1-разнообразия равно S₁ = 1 + 1 + 1 + 1 + 1 = 5.

2-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из двух дней.

Значение 2-разнообразия равно S₂ = 2 + 2 + 2 + 2 = 8.

3-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из трех дней.

Значение 3-разнообразия равно S₃ = 3 + 3 + 2 = 8.

4-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из четырех дней.

Значение 4-разнообразия равно S₄ = 3 + 3 = 6.

5-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из пяти дней.

Значение 5-разнообразия равно S₅ = 3.

Примеры тестов

5
1 3 2 1 2

5 8 8 6 3 

3
10 10 10

3 2 1 

Задача D. Олимпиада для роботов ≡

Условие

Жюри чемпионата по скоростному вычислению булевых функций среди роботов готовит задания для участников.

Задание для роботов представляет собой таблицу из m строк и n столбцов, каждая ячейка которой содержит целое число. Обозначим число в i-й строке, j-м столбце таблицы как x_i,j. В каждом столбце значения в ячейках таблицы образую перестановку чисел от 0 до m − 1. Иначе говоря, числа в каждом столбце различны: если i ≠ k, то x_{i, j} ≠ x_{k, j} для всех j, и выполнено условие 0 ≤ x_i,j < m.

Для каждого столбца таблицы задаётся значение порога — целое неотрицательное число z_j от 0 до m. В качестве аргументов булевых функций, которые будут вычислять участники олимпиады, используются значения логических выражений x_i,j < z_j. Значение такого логического выражения равно 1, если неравенство выполнено, иначе оно равно 0.

В процессе соревнования участники вычисляют значения m булевых функций — по одному для каждой строки. Каждая булева функция задаётся в виде бесповторной монотонной линейной программы (БМЛП).

Рассмотрим БМЛП для i-й строки таблицы. Она представляет собой последовательность из n − 1 инструкции, пронумерованных от 1 до n − 1, p-я инструкция задаётся тремя числами: a_p, b_p и op_p. Число op_p принимает два возможных значения: 1 для операции and  — логическое "и", 2 для операции or  — логическое "или". Числа a_p и b_p являются номерами аргументов p-й инструкции, выполнены неравенства 1 ≤ a_p, b_p < n + p.

Рассмотрим массив val[1..2 n − 1], каждое из значений которого равно 0 или 1. Проинициализируем значения val[1]..val[n] с использованием порогов, val[j] = 1, если x_i,j < z_j, иначе val[j] = 0. Значение val[n + p] вычисляется с использованием p-й инструкции.

• Если op_p = 1, то val[n + p] = (val[a_p] and al[b_p]), то есть значение val[n + p] равно 1 если и только если каждое из значений val[a_p] и val[b_p] равно 1.
• Если op_p = 2, то val[n + p] = (val[a_p] or al[b_p]), то есть значение val[n + p] равно 1 если и только если хотя бы одно из значений val[a_p] и val[b_p] равно 1.

При этом программа является бесповторной, а именно все 2 n − 2 значений a_p и b_p для p от 1 до n − 1 различны. Иначе говоря, a_p ≠ b_p, а если p ≠ q, то a_p ≠ a_q, a_p ≠ b_q, b_p ≠ a_q и b_p ≠ b_q.

Результатом исполнения программы является значение val[2 n − 1].

Жюри олимпиады подготовило таблицу x_i,j, выбрало булевы функции для каждой строки и записало их в виде БМЛП. Теперь осталось выбрать значение порога для каждого столбца, чтобы получить задание для олимпиады. Жюри считает задание сбалансированным, если ровно s из m программ для строк таблицы возвращают единицу, а остальные m − s возвращают ноль. Ваша задача — помочь жюри найти подходящие значения порогов.

Требуется написать программу, которая по заданным значениям в ячейках таблицы и БМЛП для строк таблицы определяет такие значения порогов z_j, чтобы значение ровно s из m заданных функций было равно 1. Можно доказать, что при описанных в условии задачи ограничениях требуемые значения порогов всегда можно подобрать.

Формат входных данных

В первой строке входных данных заданы целые числа n, m и s (1 ≤ n ≤ 3 ⋅ 10⁵, 1 ≤ m ≤ 3 ⋅ 10⁵, n ⋅ m ≤ 3 ⋅ 10⁵, 0 ≤ s ≤ m).

Далее следует m блоков по n − 1 строке в каждом, каждый блок задает бесповторную монотонную линейную программу для одной строки таблицы. В каждом блоке p-я строка содержит 3 целых числа: a_p, b_p и op_p (1 ≤ a_p < n + p, 1 ≤ b_p < n + p, гарантируется, что в одном блоке все значения a_p и b_p попарно различны, op_p = 1 или op_p = 2).

Последние m строк задают таблицу, i-я строка содержит n целых чисел, j-е из которых равно x_{i, j} (0 ≤ x_{i, j} ≤ m − 1, в каждом столбце все числа различны, то есть если i ≠ k, то x_{i, j} ≠ x_{k, j} для всех j).

Формат выходных данных

Выведите n целых чисел — искомые значения порогов z₁, z₂, …, z_n (0 ≤ z_j ≤ m). Если подходящих вариантов несколько, выведите любой из них.

Ограничения

1 ≤ n ≤ 3 ⋅ 10⁵, 1 ≤ m ≤ 3 ⋅ 10⁵, n ⋅ m ≤ 3 ⋅ 10⁵, 0 ≤ s ≤ m

1 ≤ a_p < n + p, 1 ≤ b_p < n + p, гарантируется, что в одном блоке все значения a_p и b_p попарно различны, op_p = 1 или op_p = 2

1 ≤ t_i ≤ 10⁹, 1 ≤ k_i ≤ 10¹⁸

0 ≤ x_{i, j} ≤ m − 1, в каждом столбце все числа различны, то есть если i ≠ k, то x_{i, j} ≠ x_{k, j} для всех j

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Замечание

В примере в таблице три строки, каждой соответствует формула. Необходимо найти четыре порога так, чтобы ровно две формулы возвращали 1, а оставшаяся — 0.

Рассмотрим, как будет вычисляться массив val для первой строки.

Первые четыре значения вычисляются на основе чисел в этой строке и порогов:

• val[1] = (x_1,1 < z₁) = (0 < 0) = 0;
• val[2] = (x_1,2 < z₂) = (1 < 1) = 0;
• val[3] = (x_1,3 < z₃) = (2 < 2) = 0;
• val[4] = (x_1,4 < z₄) = (2 < 3) = 1.

Далее выполняем линейную программу для первой строки:

• val[5] = (val[1] and val[2]) = (0 and 0) = 0;
• val[6] = (val[3] and val[4]) = (0 and 1) = 0;
• val[7] = (val[5] or val[6]) = (0 or 0) = 0.

Таким образом значение булевой функции для первой строки равно 0. Кстати, если эту функцию записать формулой, то получится:

(((x_1,1 < z₁) and (x_1,2 < z₂)) or ((x_1,3 < z₃) and (x_1,4 < z₄))).

Аналогично, булева функция для второй строки равна:

((((x_2,1 < z₁) or (x_2,2 < z₂)) and (x_2,3 < z₃)) or (x_2,4 < z₄)),

а для третьей строки:

(((x_3,1 < z₁) and (x_3,4 < z₄)) or ((x_3,2 < z₂) and (x_3,3 < z₃))).

При подстановке порогов z₁ = 0, z₂ = 1, z₃ = 2, z₄ = 3 получим следующие выражения.

Вторая строка:

((((2 < 0) or (2 < 1)) and (1 < 2)) or (0 < 3)) = (((0 or 1) and 1) or 1) = (0 or 1) = 1,

Третья строка:

(((1 < 0) and (1 < 3)) or ((0 < 1) and (0 < 2))) = ((0 and 0) or (1 and 1)) = (0 or 1) = 1.

Заметим, что это не единственный подходящий набор порогов, также подойдут, например, значения z₁ = 0, z₂ = 0, z₃ = 3, z₄ = 3.

Примеры тестов

4 3 2
1 2 1
3 4 1
5 6 2
1 2 2
3 5 1
4 6 2
1 4 1
2 3 1
5 6 2
0 1 2 2
2 2 1 0
1 0 0 1

0 1 2 3

Задача E. Максимальное произведение ≡

Условие

Задан массив натуральных чисел [a₁, a₂, …, a_n]. Весом массива назовём сумму его элементов.

Необходимо разрезать заданный массив на два непустых массива [a₁, a₂, …, a_i] и [a_i + 1, a_i + 2, …, a_n] так, чтобы произведение их весов было как можно больше.

Требуется написать программу, которая по заданному массиву определяет, после какого элемента его необходимо разрезать, чтобы произведение весов получившихся массивов было максимальным.

Формат входных данных

В первой строке входных данных находится целое число n — количество элементов в массиве (2 ≤ n ≤ 2 ⋅ 10⁵). В следующей строке находятся n целых чисел a₁, a₂, …, a_n — элементы массива (1 ≤ a_i ≤ 10⁹).

Формат выходных данных

Выведите одно число — номер элемента, после которого необходимо разрезать заданный массив. Если оптимальных вариантов ответа несколько, можно вывести любой из них.

Ограничения

1 ≤ a_i ≤ 10⁹

2 ≤ n ≤ 2 ⋅ 10⁵

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Замечание

Если сделать разрез после первого элемента, произведение весов равно 1 ⋅ (2 + 3) = 5, а если после второго, то (1 + 2) ⋅ 3 = 9

Примеры тестов

3
1 2 3

2

Задача F. Планировка участка ≡

Условие

Учёные планируют участок для испытательного полигона. Участок должен иметь форму прямоугольника a × b, а полигон должен иметь форму прямоугольника c × d. С точными значениями чисел a, b, c и d ученые пока не определились, однако известно следующее:

• Длины сторон a, b, c, d должны быть натуральными числами и выражаться в километрах.
• Для безопасности эксперимента длина и ширина участка должны отличаться от значения x, то есть должны выполняться неравенства a ≠ x, b ≠ x.
• Участок будет огражден забором, а полигон должен полностью помещаться внутри участка, то есть должны выполняться следующие условия: a > c, b > d.
• Площадь участка, не занятого полигоном, должна быть ровно n квадратных километров, то есть должно выполняться следующее условие: a ⋅ b − c ⋅ d = n.

Учёные хотят понять, сколько у них способов выбрать подходящие значения a, b, c и d.

Требуется написать программу, которая по заданным n и x определяет количество способов выбрать числа a, b, c и d так, чтобы все описанные условия выполнялись.

Формат входных данных

В первой строке ввода содержится два целых числа n и x — площадь свободного участка без полигона и запрещенная длина стороны участка соответственно.

Значение x = 0 означает, что ограничений на длины сторон нет (так как длины сторон должны быть натуральными числами, и, следовательно, больше 0).

Формат выходных данных

В единственной строке выведите количество способов выбрать числа a, b, c и d так, что все описанные условия выполняются.

Ограничения

1 ≤ n ≤ 3000

0 ≤ x ≤ 3000

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

3 0

1

5 0

5

5 3

2

Задача G. Банкомат ≡

Условие

Ведётся разработка универсального банкомата, который сможет работать с любой денежной системой. Пусть в денежной системе некоторой страны используются n типов купюр, номиналы которых равны a₁, a₂, …, a_n. При этом все номиналы различны и перечислены в порядке возрастания: если i ≥ 2, то a_i − 1 < a_i, а также a₁ = 1.

Банкомат использует следующий жадный алгоритм для выдачи купюр. Пусть клиент запросил у банкомата сумму c. Изначально есть пустой набор выдаваемых купюр. На каждом шаге алгоритм добавляет в набор купюру максимально возможного номинала так, чтобы сумма номиналов купюр в наборе не превышала c. Когда сумма номиналов купюр в наборе стала равна c, алгоритм останавливается. Отметим, что, поскольку существует купюра с номиналом a₁ = 1, алгоритм всегда заканчивает работу за конечное число шагов.

Чтобы оценить эффективность данного алгоритма, требуется выяснить, какое максимальное число купюр может потребоваться выдать за один раз, если максимальная сумма, которую можно запросить, равна b. Поскольку максимальная сумма может зависеть от категории обслуживания клиента, необходимо ответить на q запросов для сумм b₁, b₂, …, b_q.

Требуется написать программу, которая по списку номиналов купюр денежной системы и максимальной сумме, которую можно запросить, определяет сумму, которую необходимо запросить в банкомате, чтобы получить максимальное число купюр, и искомое число купюр.

Формат входных данных

Первая строка содержит целое число n — количество номиналов купюр (1 ≤ n ≤ 200 000).

Вторая строка содержит n различных целых чисел a_i (1 = a₁ < a₂ < …  < a_n ≤ 10¹⁸).

Третья строка содержит целое число q — количество запросов (1 ≤ q ≤ 200 000).

Следующие q строк содержат по одному целому числу b_i (1 ≤ b_i ≤ 10¹⁸).

Формат выходных данных

Для каждого запроса выведите два числа — сумму, которую необходимо запросить в банкомате, чтобы получить максимальное число купюр, и искомое число купюр. Если существует несколько сумм, не превышающих максимального значения, для которых будет выдано максимальное число купюр, требуется вывести любую из них.

Ограничения

1 ≤ n ≤ 200000

1 = a₁ < a₂ < …  < a_n ≤ 10¹⁸

1 ≤ q ≤ 200 000

1 ≤ b_i ≤ 10¹⁸

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Замечание

• 2 будет выдано как 1 + 1,
• 8 будет выдано как 5 + 1 + 1 + 1,
• 49 будет выдано как 10 + 10 + 10 + 10 + 5 + 1 + 1 + 1 + 1.

Примеры тестов

4
1 5 10 50
3
2
8
50

2 2
8 4
49 9

Задача H. Плакаты ≡

Условие

Друзья готовятся встретить национальную команду, возвращающуюся с международной олимпиады по информатике. Для этого они подготовили множество красочных плакатов. Осталось только продумать детали поздравления.

Для того, чтобы приветствовать команду, n друзей встанут в круг. Пронумеруем их от 1 до n в порядке их расположения по кругу. Таким образом, для всех i от 1 до n − 1 друзья с номерами i и i + 1 стоят рядом, также рядом стоят друзья с номерами n и 1. У каждого из друзей есть плакат. Каждый плакат характеризуется своей красочностью — целым неотрицательным числом. Плакат у друга с номером i имеет красочность a_i.

Когда поздравление начнётся, некоторые из друзей поднимут свои плакаты и будут показывать их команде. Для того, чтобы члены команды не растерялись и смогли рассмотреть все плакаты, не должно быть четырёх или более стоящих подряд друзей с поднятым плакатом.

Друзья планируют изменять плакаты в процессе встречи. Всего будет внесено q изменений в плакаты. После i-го из них плакат друга с номером p_i будет иметь красочность v_i. После каждого из изменений друзья хотят определить, какую максимальную суммарную красочность могут иметь поднятые плакаты, если нельзя нарушать установленное ограничение.

Требуется написать программу, которая по заданной начальной красочности плакатов и последовательности их изменений определяет в начале, а также после каждого изменения, какой максимальной суммарной красочности поднятых плакатов можно добиться, не нарушая условие, что поднято не более трёх плакатов подряд.

Формат входных данных

Первая строка ввода содержит целое число n (4 ≤ n ≤ 40 000) — количество друзей.

Вторая строка содержит n целых чисел a_i (0 ≤ a_i ≤ 10⁹) — исходные значения красочности плакатов у друзей.

Третья строка содержит одно целое число q (0 ≤ q ≤ 40 000) — количество изменений плакатов, которые вносили друзья.

Каждая из следующих q строк содержит два целых числа p_i и v_i (1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹) — номер друга, плакат которого изменился, и новая красочность этого плаката.

Формат выходных данных

Выведите q + 1 число. Перед первым изменением, а также после каждого изменения плакатов выведите одно целое число — максимальное суммарное значение красочности поднятых плакатов, если нельзя поднимать больше трёх плакатов подряд.

Ограничения

4 ≤ n ≤ 40 000

0 ≤ a_i ≤ 10⁹

0 ≤ q ≤ 40 000

1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснения

Перед первым изменением плакаты следует поднять друзьям с номерами 2, 4, 5, 6. Суммарная красочность поднятых плакатов будет равняться 17.

После первого изменения плакат друга с номером 6 имеет красочность 0. Теперь плакаты следует поднять друзьям с номерами 1, 3, 4, 5. Суммарная красочность будет равняться 13.

После второго изменения плакат друга с номером 2 имеет красочность 5. Плакаты следует поднять друзьям с номерами 1, 2, 4, 5. Суммарная красочность будет равняться 15.

Примеры тестов

6
1 2 3 4 5 6
2
6 0
2 5

17
13
15