34717번 - 코인과 쿼리

문제

시루는 $N$일 동안의 코인 가격 $A_1, A_2, \cdots, A_N$을 예측할 수 있는 능력을 갖게 되었다. 시루는 이 능력을 토대로 분할 매수 전략을 이용해 이득을 극대화하려고 한다. 분할 매수 전략이란, 1ドル \le i \le j \le N$을 만족하는 두 정수 $i, j$를 정한 다음, $i$번째 날부터 $j$번째 날까지 매일 코인을 1개씩 매수하고, $j$번째 날에 보유한 모든 코인을 한 번에 매도하는 방식을 의미한다.

예를 들어서 7일 동안의 코인 가격이 9,ドル 8, 2, 4, 3, 5, 3$이라고 하자. $i = 3, j = 6$으로 정하면 4일 동안 4개의 코인을 2ドル+4+3+5=14$원에 매수한 다음 모든 코인을 개당 5ドル$원에 매도하므로 총 5ドル \times 4 - 14 = 6$원의 이득을 얻을 수 있다. 거래를 하지 않을 수도 있으며, 이때의 이익은 0원이다.

시루는 여러가지 거래 시나리오를 고려해 보려고 한다. 구체적으로, 세 정수 $L, R, X$가 주어지면 매수 시작일 $i$가 $L$ 이상 $R$ 이하이고 매도일 $j$가 $X$가 되도록 $i, j$를 선택할 때 얻을 수 있는 최대 이익을 구하고자 한다.

$N$일 동안의 코인 가격과 $Q$개의 거래 시나리오가 주어지면, 각 시나리오에서 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하라. 이익을 얻을 수 있는 거래가 없는 경우 아무것도 하지 않을 수 있으며, 이때의 답은 0임에 유의하라.

입력

첫째 줄에 거래일 수 $N$과 시나리오 수 $Q$가 공백으로 구분되어 주어진다.

그다음 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. 이는 $i$번째 날의 코인 가격이 $A_i$임을 의미한다.

이어지는 $Q$개의 줄의 $i$번째 줄에는 $i$번째 거래 시나리오에 대한 정보를 나타내는 세 개의 정수 $L, R, X$가 공백으로 구분되어 주어진다.

출력

$Q$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에 $i$번째 시나리오에 대한 답을 출력한다.

제한

• 1ドル \le N, Q \le 500,000円$
• 1ドル \le A_i \le 1,000円,000円$ (1ドル \le i \le N$)
• 1ドル \le L \le R \le X \le N$

노트