Siz bu suallara cavab verə bilərsinizmi - 1

Verilmiş tam ədədlər ardıcıllığı a[1], a[2], ..., a[n] (|a[i]| ≤ 15007, 1 ≤ n ≤ 50000) şəklindədir. Sorğular aşağıdakı kimidir:

Sorğu(x, y) = MAX {a[i] + a[i+1] + ... + a[j], x ≤ i ≤ j ≤ y}

Sizdən m sorğunun cavablarını tapmaq tələb olunur.

Giriş məlumatları

Birinci sətir n dəyərini ehtiva edir. İkinci sətirdə ardıcıllığın n tam ədədi verilir. Üçüncü sətir sorğuların sayını m ehtiva edir. Daha sonra m sətir gəlir, burada hər bir i-ci sətir iki ədəd x[i] və y[i] ehtiva edir.

Çıxış məlumatları

Hər bir sorğunun cavabını ayrı sətirdə çıxarın.

Nümunələr