Это простая версия задачи. Различия между версиями заключаются в том, что в простой версии нет запросов обмена. Вы можете делать взломы, только если обе версии задачи сданы.
Пикачу — милый и дружелюбный покемон, живущий в стае диких пикачу.
Однако недавно стало известно, что команда R хочет украсть всех этих покемонов! Тренер покемонов Андрей решил помочь Пикачу собрать армию для борьбы с командой R.
В первую очередь Андрей посчитал всех покемонов: их оказалось ровно $$$n$$$ штук. Затем он установил силу каждого покемона, и так получилось, что $$$i$$$-й покемон имеет силу, равную $$$a_i$$$, и силы всех покемонов различны.
В качестве армии Андрей может выбрать любую непустую подпоследовательность покемонов. Иными словами, Андрей выбирает какой-то массив $$$b$$$ из $$$k$$$ индексов таких, что $$$1 \le b_1 < b_2 < \dots < b_k \le n$$$, и его армия будет состоять из покемонов с силами $$$a_{b_1}, a_{b_2}, \dots, a_{b_k}$$$.
Сила армии вычисляется как знакопеременная сумма элементов подпоследовательности, то есть $$$a_{b_1} - a_{b_2} + a_{b_3} - a_{b_4} + \dots$$$.
Андрей экспериментирует с построением покемонов. Он $$$q$$$ раз меняет двух покемонов местами, а именно, в $$$i$$$-й раз он менял местами покемонов с номерами $$$l_i$$$ и $$$r_i$$$.
Обратите внимание, в этой версии задачи $$$q=0$$$.
Андрею надо знать: какую максимальную силу армии он мог получить при начальной расстановке покемонов, а также после каждого изменения строя?
Помогите Андрею и покемонам, иначе команде R удастся воплотить в жизнь свой коварный план!
Каждый тест содержит несколько наборов входных данных.
В первой строке находится одно целое положительное число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Описание наборов входных данных приведено ниже.
В первой строке каждого набора входных данных находятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 3 \cdot 10^5, q = 0$$$) — количество покемонов и количество обменов соответственно.
Во второй строке находятся $$$n$$$ различных целых положительных чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — силы покемонов.
$$$i$$$-я из следующих $$$q$$$ строк содержит два целых положительных числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — номера обмениваемых покемонов в $$$i$$$-й операции.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$, а также сумма $$$q$$$ по всем тестовым случаям не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$q+1$$$ число — максимально возможную силу армии до изменений и после каждого изменения.
3 3 0 1 3 2 2 0 1 2 7 0 1 2 5 4 3 6 7
3 2 9
В третьем наборе входных данных мы можем выбрать армию следующим образом: [1 2 5 4 3 6 7], при этом ее итоговая сила будет $$$5−3+7=9$$$.
| Codeforces Round 672 (Div. 2) |
|---|
| Закончено |
