#2756 재재새와 재재새 부분집합

1 s   128 MB  

Description

재재새는 최근 집합에 빠져있다.

 

특히, 집합에서는 부분집합에 빠져 있으며,

 

부분집합 중에서도, 연속된 원소들을 갖는 부분집합에 빠져있다.

 

이제부터, 이런 부분집합을 재재새 부분집합이라고 명명하겠다.

 

일단, 예를 들어보자.

 

S = {1, 2, 3, 4, -5, 2, 4, 6, 7}

 

집합 S의 재재새 부분집합의 예시는 다음과 같다.

 

{1}, {1,2}, {1,2,3}, {2,3,4,-5}, $ \dots $

 

 

재재새는 특정 구간이 주어졌을때, 그 구간 내의 재재새 부분집합 중에서 합의 최댓값을 구하고 싶어한다.

 

위의 집합 S의 구간 [2, 6]의 재재새 부분집합 중, 최댓값은 {2,3,4}의 합인 9이다.

 

N, M이 순서대로 입력되며,

N개의 집합 원소가 순서대로 입력된다.

M개의 쿼리의 구간이 주어진다.

 

쿼리내의 재재새 부분집합 중, 최댓값을 구해주면 된다.

Input

$1 \leq N \leq 100000$ $1 \leq M \leq 100000$

$ -1000000 \leq e_i \leq 1000000 ( 1 \leq i \leq N ) $

$ 1 \leq a_i, b_i \leq N $

Output

쿼리의 재재새 부분집합의 합 중 최댓값을 한 줄에 하나씩 출력한다.

Sample Input

Sample Output

5 3
1 2 3 -1 3
1 5
3 4
4 5
8
3
3

Source

wowoto9772