Cerința

Se dă un vector de N numere naturale nenule, indexat de la 1.
Se cere să se raspundă la Q interogări de tipul:

• pentru un interval [l, r] din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval.

Într-un interval [l, r], puteți crește sau micșora fiecare element cu costul x unde x este diferența dintre valoarea nouă și valoarea inițială. Costul total este suma acestor costuri.

Date de intrare

• pe prima linie numărul N.
• pe a doua linie N numere naturale nenule : \({x}_{1} \), \({x}_{2} \), … \({x}_{N} \).
• pe a treia linie numărul Q.
• pe următoarele Q linii 2 numere: l, r.

Date de ieșire

Se vor afișa Q numere pe fiecare linie, reprezentând constul total minim, al fiecărui interval l r.

Restricții și precizări

• 1 ≤ N, Q ≤ 100.000
• 1 ≤ l ≤ r ≤ 100.000
• 1 ≤ \({x}_{i} \) ≤ 1.000.000.000

Exemplu:

Intrare

9
3 2 16 15 12 6 20 4 5
3
2 7
2 2
3 8

Ieșire

31
0
29

Explicație

Pentru intervalul [2, 7], costul total minim este 31, deoarece egalizăm fiecare număr din interval cu 12.
Pentru intervalul [2, 2], costul total minim este 0, deoarece avem un singur element în interval.
Pentru intervalul [3, 8], costul total minim este 29, deoarece egalizăm fiecare număr din interval cu 12.