1083

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int* cost;
    int n,i,q,a,b,k,total=0,sell;
    cost=(int*)malloc(sizeof(int)*1000000);
    scanf("%d",&n);
    for(i=0; i<n; i++) scanf("%d",&cost[i]);
    scanf("%d",&q);
    for(k=0; k<q; k++)
    {
        scanf("%d%d",&a,&b);
        a--;
        b--;
        for(i=a; i<b; i++)
        {
            if(i>=b) break;
            //printf("\n--test %d\n",cost[i]);
            if(cost[i]<cost[i+1])
            {
                sell=i+1;
                while(1)
                {
                    if(sell>=b) break;
                    if(cost[sell]<cost[sell+1])
                    {
                        sell++;
                    }
                    else break;
                }
                total+=cost[sell]-cost[i];
                i=sell;
                //printf("i== %d",i);
            }
        }
        printf("%d",total);
        total=0;
    }

    return 0;
}