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

Пикачу — милый и дружелюбный покемон, живущий в стае диких пикачу.

Однако недавно стало известно, что команда 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 удастся воплотить в жизнь свой коварный план!