Give a sequence a[1], a[2], ..., a[n] (|a[i]| <= 15000, n <= 50000). Let function q(x, y) = max { sum(a[i]+a[i+1]+...+a[j]), x <= i <= j <= y }. There are m query form x y (1 <= x <= y <= n). (m <= 50000) calculate q(x, y)

Sorry for my bad English.