Дан массив а[1], a[2], ..., a[N]. ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ).
Запрос определяется по паре чисел x, y:
Запрос(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }
Даётся M запросов.

Решения за O(N*M) - TLE, нужно что-то побыстрей.

Заранее спасибо.

Upd: Проблема решена. Всем спасибо!