Triple Jump timer 4s memory 512MB

매우 긴 도로에 1부터 N까지의 번호가 붙어있는 N개의 위치가 있다.

각 위치마다 도로의 강도가 다를 수 있으며, i번째 (1 ≤ i ≤ N) 위치의 도로의 강도는 A_i이다.

스포츠 스타 준혁이는 3단 점프를 하려고 한다.

3단 점프는 3개의 연속된 점프로 이루어 져 있다.

준혁이가 a, b, c번째 위치에서 점프를 하려고 하면, 다음 조건을 만족해야 한다:

- a < b < c. 즉, 점프하는 곳의 번호는 증가해야 한다.

- b − a ≤ c − b. 즉, 첫번째 점프의 거리가 두번째 점프의 거리보다 작거나 같아야 한다.

준혁이는 Q번의 3단 점프를 하려고 한다.

j번째(1 ≤ j ≤ Q)의 3단 점프에서는 L_j번째 이상 R_j번째 이하의 위치에서만 3단 점프를 해야 한다.

즉 L_j ≤ a < b < c ≤ R_j가 성립하여야 한다.

준혁이는 강도가 높은 곳에서 3단 점프를 하고 싶어 한다.

각 3단 점프 마다 준혁이는 자신이 점프를 하는 세 위치에서의 강도의 합의 최댓값을 알고 싶다.

위치의 정보와 3단 점프의 정보가 주어졌을 때, 각 점프마다 준혁이가 점프를 하는 세 위치에서의 강도의 합의 최댓값을 구하는 프로그램을 작성하여라.