Это простая версия задачи. Различия между версиями заключаются в том, что в простой версии нет запросов обмена. Вы можете делать взломы, только если обе версии задачи сданы.
Пикачу — милый и дружелюбный покемон, живущий в стае диких пикачу.
Однако недавно стало известно, что команда 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 удастся воплотить в жизнь свой коварный план!