Ən böyük cəm
a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 10^8, 2 ≤ n ≤ 10^5) ardıcıllığı verilir. İki tip əməliyyat vardır və onlar növbəti şəkildə təyin olunur:
Yeniləmə:
Bu girişdə 'U' kimi verilə bilər və boşluqdan sonra iki i və x tam ədədləri verilir.
U i x, 1 ≤ i ≤ n и 0 ≤ x ≤ 10^8
Bu əməliyyat x üçün a[i] qiymətlərini qurur.
Sorğu:
Bu girişdə 'Q' kimi verilə bilər və boşluqdan sonra iki i və j tam ədədləri verilir.
Q x y, 1 ≤ x < y ≤ n
Siz elə i və j tapmalısınız ki, x ≤ i, j ≤ y və i ≠ j, a[i] + a[j] cəmi ən böyük olsun. a[i] + a[j] cəmini verin.
Giriş verilənləri
İlk sətir ardıcıllığın uzunluğunu ifadə edən n tam ədədini ehtiva edir. Növbəti sətir boşluqla ayrılmış n sayda a[i] tam ədədlərini ehtiva edir. Növbəti sətir əməliyyatların sayını ifadə edən q (q ≤ 10^5) tam ədədini ehtiva edir. Növbəti q sayda sətirlər əməliyyatları ehtiva edir.
Çıxış verilənləri
Ayrı-ayrı sətirdə hər bir sorğu üçün maksimum cəmi verməli.