Чи можете Ви відповісти на ці питання - 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}

Вихідні дані

Для кожного запиту вивести відповідь як вимагається в задачі.

Приклади