JOI Open 2019 #1- Triple Jump > 문제은행 : 정보올림피아드&알고리즘


4684 : Triple Jump

제한시간
4000 ms   
메모리제한
512 MB   
해결횟수
1 회   
시도횟수
1 회   

문제

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

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

 

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

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

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

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

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

 

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

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

즉 Lj ≤ a < b < c ≤ Rj가 성립하여야 한다.

 

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

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

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


입력형식

1번 줄 : N

2번 줄 : A1 ... AN

3번 줄 : Q

4번 ~ Q + 3번 줄 : Lj Rj

​ 

3 ≤ N ≤​ 500 000

1 ≤​ Ai ≤​ 1 000 000 000

1 ≤​ Q ≤​ 500 000

1 ≤​ Lj < Lj + 2 ≤​ Rj ≤​ N


출력형식

Q개의 줄에 각각 준혁이가 점프를 하는 세 위치에서의 도로 강도의 합의 최댓값을 출력하여라.


입력 예

5
5 2 1 5 3
3
1 4
2 5
1 5

출력 예

12
9
12


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP