Можете ли Вы ответить на эти вопросы - 3

Задана последовательность целых чисел a_1, a_2, ..., a_n (|a_i| ≤ 10000 , 1 ≤ n ≤ 50000). Над ней Вам следует выполнить m (m ≤ 50000) операций:

• модифицировать i-ый элемент последовательности

• для заданных x и y вывести MAX {a_i + a_{i+1} + ... + a_j, x ≤ i ≤ j ≤ y}

Входные данные

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность a_1, a_2, ..., a_n. Третья строка содержит число m. Следующие m строк содержат запросы вида:

• 0 x y: изменить a_x на y (|y| ≤ 10000).

• 1 x y: вывести MAX {a_i + a_{i+1} + ... + a_j, x ≤ i ≤ j ≤ y}

Выходные данные

Для каждого запроса вывести ответ как требуется в задаче.

Примеры