Alan's Gold

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 3.5s
Memory limit: 512M

Problem types

Alan has recently made a deal with a Nigerian prince, and is now faced with N boxes full of gold. The boxes are equally distant from each other, with the N^{th} box closest to him. However he has not come prepared, and his truck only has space for 2 boxes of gold.

Each of the boxes of gold has a value A_i, which is the value of the gold contained in it.

Unfortunately, Alan is also extremely lazy, and the boxes with greater value are also heavier due to their higher gold content. Thus, for each step Alan takes with a box, the value of taking that box decreases, as he loses the will to continue.

Alan has decided that the optimal way for him to choose 2 boxes is to maximize (A_i + A_j)\cdot i\cdot j, where i and j are the indices of the boxes he takes. This way, he believes he will get the maximum revenue to effort ratio.

The Nigerian Prince is very sketchy, however, and Alan doesn't know the exact value of any box at any given time. He does have an estimate of the value of each box which changes over time.

There will be Q queries in which Alan will re-evaluates the value of box x_j, and decides it is more likely to be of value v_j. For each query, Alan would like to know the maximal value of (A_i+A_j)\cdot i\cdot j he can obtain. Can you help Alan?

Input Specification

The first line of input will contain two integers N\ (1 \leq N \leq 5\cdot 10^5), and Q\ (1 \leq Q \leq 5\cdot 10^5), the number of boxes and queries.

The next line will contain N integers A_i\ (1 \leq A_i \leq 10^6), the original values of the gold boxes.

The next Q lines will contain 2 integers x_j\ (1 \leq x_j \leq N), and v_j\ (1 \leq v_j\leq 10^6).

Ouput Specification

You are to output Q lines, the answers to Alan's queries.


Subtask 1 (5%)

N,Q \leq 500

Subtask 2 (15%)

N,Q \leq 3000

Subtask 3 (30%)

Q = 10

Subtask 4 (50%)

No further constraints.

Sample Input

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

Sample Output



There are no comments at the moment.