************************************max, min, sum structure ..

struct st
 {
  lli maxi;
  lli mini;
  lli sum;
 } seg[1000000];


 int arr[1000000];
 void build(int idx,int  start,int end)
  {
  if(start>end)
  return;
  else if(start==end)
   {
 
    seg[idx].maxi=arr[start];
    seg[idx].mini=arr[start];
    seg[idx].sum=arr[start];
    return ;
 }
 int mid=(start+end)/2;
 build(2*idx,start,mid);
 build(2*idx+1,mid+1,end);
 seg[idx].maxi=max(seg[2*idx].maxi,seg[2*idx+1].maxi);
 seg[idx].mini=min(seg[2*idx].mini,seg[2*idx+1].mini);
 seg[idx].sum=seg[2*idx].sum+seg[2*idx+1].sum;
 
  }
 
  st qry(int idx,int start,int end,int qs,int qe)
   {
    if(start>end || qs>end || qe<start)
     {
      st temp;
      temp.maxi=INT_MIN;
      temp.mini=INT_MAX;
      temp.sum=0;
      return temp;
 }

 else if(start>=qs && end<=qe)
  {
  return seg[idx];
  }
 
  int mid=(start+end)/2;
  st l=qry(2*idx,start,mid,qs,qe);
  st r=qry(2*idx+1,mid+1,end,qs,qe);
  st ret;
 
 ret.maxi=max(l.maxi,r.maxi);
 ret.mini=min(l.mini,r.mini);
 ret.sum=l.sum+r.sum;
 return ret;

   }