Hungry Tiger

F. Hungry Tiger

No Submission Yet

Problem Statement

The thought of Domino's pizza was too alluring, so CodeTiger eventually succumbed to his hunger and went to get food. At the LHS cafeteria (horrific btw), CodeTiger discovers \(N\) possible lunch options labeled from \(1\) to \(N\), each with a tastiness value of \(a_i\). Of course, since we all know CodeTiger is a greedy tiger, one single lunch cannot satiate CodeTiger's hunger, but rather all of them. Luckily for the other LHS students, CodeTiger is rather picky - he must eat from left to right, and each lunch must be tastier than the prior. However, being so greedy, CodeTiger will eat whatever first satisfies the condition, even if it leads to a suboptimal sum of tastiness.

You are given \(Q\) queries in the form of \([L,R]\). For each query, find the maximum sum of tastiness CodeTiger can eat between lunch \(L\) and \(R\) if he can start at any lunch. Formally, find the maximum sum \(\sum_{i=1}^m a_{x_i}\) of subsequences with indices \(L \leq x_1 < x_2 < \cdots < x_m \leq R\) where \(x_i\) is the minimum index with \(x_{i-1} < x_i \leq R\) such that \(a_{x_{i-1}} < a_{x_i}\) for all \(1 < i \leq m\).

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb


\(N,Q \leq 3 \cdot 10^5\)
\(1 \leq a_i \leq 10^{12}\)

Input Format

The first line contains four integers, \(N\), \(Q\)
The second line contains \(N\) integers, the \(i\)th integer is the tastiness value \(a_i\)
The last \(Q\) lines each describe a range query with 2 integers: left endpoint \(L\) and right endpoint \(R\).

Output Format

Output \(Q\) lines of integers, with the \(i\)th line being the answer to the \(i\)th query.

Sample Input

6 3
4 2 7 5 6 8
1 6
1 2
3 5

Sample Output


Sample Explanation

Note that for \([1,6]\), if tiger starts at index 2, even though it is better to take \(2,5,6,8\), because CodeTiger is greedy, he instead takes \(2,7,8\) since \(7\) is nearer than \(5\).

Credit: CodeTiger

Contact Us
LIT Discord Server