It's known that

f(1, j) = a[j], 1 ≤ j ≤ n.

f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n.

The problem is to calculate f(xi,yi).

Obviously, the final route of [xi,yi] would be like:

|

|

|

|

\

\

\

   \

     \

So f(xi,yi) = min( a[j] * (xi — yi + j) + sum(yi) — sum(j)), yi — xi < j <= yi.

sum(i) represents Σa[k], 1 <= k <= i.

For a query (xi, yi):

Marks that g[j] = a[j] * (xi — yi + j) + sum(yi) — sum(j), yi — xi < j <= yi.

A is better than B (a[A] < a[B]) if and only if g[A] < g[B], which equals

(a[A] * A — sum[A]) — (a[B] * B — sum[B])

------------------------------------------- > yi — xi

a[A] - a[B]

If a lower convex hull between (yi — xi + 1) and yi is built, the problem will be solved by method of bisection.

For there are many queries, I used a segment tree to store the convex hull.

To build the convex hull, a balance tree can be used but not necessary. I sorted array a by merge sort, and built the convex hull using a stack.

Solving all queries online, The time complexity is O(nlgn + mlg^2n). It can be decline to O(nlgn + m) if produced offline.