«Т-поколение» решило закупить мерч на различные нужды, таким образом, у них есть \(n\) различных кофт, пронумерованных от \(1\) до \(n\). Где \(i\)-я кофта имеет размер \(a_i\). Теперь им нужно отправить какой-нибудь подотрезок кофт на олимпиаду. Необходимо, чтобы кофты подошли как можно большему количеству людей, но при том, чтобы не пришлось брать их слишком много.
Им нужно выбрать два индекса \(l\) и \(r\) (\(1 \le l \le r \le n\)) и максимизировать значение удобства, равное \(\)\operatorname{max} (a_l, a_{l + 1}, \ldots, a_r) - \operatorname{min} (a_l, a_{l + 1}, \ldots, a_r) - (r - l),\(\) то есть, разброс размеров минус количество кофт.
Иногда размеры кофт меняются, известно, что было \(q\) изменений размеров. В каждом изменении размер некоторой \(p\)-й кофты становится равным \(x\).
Помогите кружку и определите максимальное значение удобства среди всех возможных пар \((l, r)\) изначально, а также после каждого изменения размера.
Выходные данные
Для каждого набора входных данных выведите максимальное значение удобства по всем возможным парам \((l, r)\) до всех действий, а также после изменения размеров.