Это сложная версия задачи. Различия между версиями заключаются в том, что в простой версии нет запросов обмена. Вы можете делать взломы только если обе версии задачи сданы.
Пикачу — милый и дружелюбный покемон, живущий в стае диких пикачу.
Однако недавно стало известно, что команда 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\).
Андрею надо знать: какую максимальную силу армии он мог получить при начальной расстановке покемонов, а также после каждого изменения строя?
Помогите Андрею и покемонам, иначе команде R удастся воплотить в жизнь свой коварный план!
Выходные данные
Для каждого набора входных данных выведите \(q+1\) число — максимально возможную силу армии до изменений и после каждого изменения.
Примечание
Рассмотрим третий набор входных данных:
Изначально мы можем выбрать армию следующим образом: [1 2 5 4 3 6 7], при этом ее итоговая сила будет \(5-3+7=9\).
После первого изменения выбор армии будет таким: [2 1 5 4 3 6 7], при этом ее итоговая сила будет \(2-1+5-3+7=10\).
Далее выбор армии будет таким: [2 1 5 4 3 7 6], при этом ее итоговая сила будет \(2-1+5-3+7=10\).
После третьего изменения армию можно выбрать так: [2 1 4 5 3 7 6], при этом ее итоговая сила будет \(2-1+5-3+7=10\).
Далее выбор армии будет таким: [1 2 4 5 3 7 6], при этом ее итоговая сила будет \(5-3+7=9\).
После всех запросов выбор армии будет таким: [1 4 2 5 3 7 6], при этом ее итоговая сила будет \(4-2+5-3+7=11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 1
1 3 2
1 2
2 2
1 2
1 2
1 2
7 5
1 2 5 4 3 6 7
1 2
6 7
3 4
1 2
2 3
|
3
4
2
2
2
9
10
10
10
9
11
|