Вам дана последовательность из \(n\) целых чисел \(a_1, a_2, \ldots, a_n\).
Вы должны построить две последовательности целых чисел \(b\) и \(c\) длины \(n\), которые удовлетворяют условиям:
- для всех \(i\) (\(1\leq i\leq n\)) \(b_i+c_i=a_i\);
- \(b\) неубывающая, что означает, что для всех \(1<i\leq n\), выполнено \(b_i\geq b_{i-1}\);
- \(c\) невозрастающая, что означает, что для всех \(1<i\leq n\), выполнено \(c_i\leq c_{i-1}\).
Вы хотите минимизировать \(\max(b_i,c_i)\). Другими словами, вы хотите минимизировать максимум чисел в последовательностях \(b\) и \(c\).
Также будет сделано \(q\) изменений, \(i\)-е изменение описывается тройкой чисел \(l,r,x\). Вы должны добавить \(x\) к \(a_l,a_{l+1}, \ldots, a_r\).
Вы должны найти минимальное значение \(\max(b_i,c_i)\) для изначальной последовательности и для последовательности после каждого изменения.