Tnia

#include <iostream>
#include <fstream>

using namespace std;

ifstream in("tnia.in");
ofstream out("tnia.out");

int searchbin1(long long h[], long long left, int right, long long value)
{
    if(h[left]>=value)
        return left-1;
    int mid;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(value<=h[mid])
            right=mid-1;
        else
            left=mid+1;
    }
    return right;
}
int searchbin2(long long h[], long long left, long long right, long long value)
{
    if(h[right]<value)
        return right;
    int mid;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(value<=h[mid])
            right=mid-1;
        else
            left=mid+1;
    }
    return right;
}
long long int s[100001];
int main()
{
    long long  h[100001], n, m, q, i, j, ls, cs, lj, cj, p1, p2;
    long long int sum;
    in>>n>>m;
    for(i=1; i<=n; i++)
    {
        in>>h[i];
        s[i]=s[i-1]+h[i];
    }
    in>>q;
    for(i=1; i<=q; i++)
    {
        in>>cs>>ls>>cj>>lj;
        if(ls>lj)
          swap(ls, lj);
        if(cs>cj)
          swap(cs, cj);
        sum=0;
        if(cs==cj)
        {
            if(h[cs]<ls)
                sum=0;
            else if(h[cs]<lj)
                sum=h[cs]-ls+1;
            else
                sum=lj-ls+1;
        }
        else
        {
            p1=searchbin1(h, cs, cj, ls);
            p2=searchbin2(h, cs, cj, lj)+1;
            sum+=s[p2-1]-s[p1]-(p2-p1-1)*(ls-1);
            sum+=(cj-p2+1)*(lj-ls+1);
        }
        out<<sum<<"\n";
    }
}