title: Sum of all Maximum and minimum in all segments
body: <p>I am doing a problem in which there is a need to find sum of maximum elements in a segment - sum of minimum elements in a segment.I tried using Sparse Table ,but it is two slow for the time limit.So i did something like this:</p>
  
  <p>If <code>n=4</code> segments are <code>[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]</code>.
  The problem is similar to an RMQ problem but i have to do it for all segments and find the </p>
  
  <p><code>sum=max(a[1],a[2])+
  max(a[1],a[2],a[3])+max(a[1],a[2],a[3],a[4])+max(a[2],a[3])+m‌​ax(a[2],a[3],a[4])+max(a[3],a[4])-min(a[1],a[2])+min(a[1],a[2],a[3])+min(a[1],a[2‌​],a[3],a[4])+min(a[2],a[3])+min(a[2],a[3],a[4])+min(a[3],a[4])</code></p>
  
  <pre><code>for(i=1;i&lt;n;i++)
  {
      maxtilli[i-1]=INT_MIN;
      mintilli[i-1]=INT_MAX;
      for(k=1,j=i;j&lt;=n;k++,j++)
      {
          if(a[j]&gt;maxtilli[k-1])
          {
              maxtilli[k]=a[j];
          }
          else
          {
               maxtilli[k]=maxtilli[k-1];
          }
  
          if(a[j]&lt;mintilli[k-1])
          {
              mintilli[k]=a[j];
          }
          else
          {   
              mintilli[k]=mintilli[k-1];
          }
          if(i!=j)
          { 
              ans+=(maxtilli[k]-mintilli[k]);
          }
      }
  }
  </code></pre>
  
  <p>Here <code>n</code> is of the order of 100,000. So is there any way to optimize it.</p>
  
  <p>Suppose <code>n=4</code> then segments are <code>[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]</code>.</p>
  
  <p>The thing required is 
  <code>sum=max(a[1],a[2])+max(a[1],a[2],a[3])+max(a[1],a[2],a[3],a[4])+max(a[2],a[3])+m‌​ax(a[2],a[3],a[4])+max(a[3],a[4])-min(a[1],a[2])+min(a[1],a[2],a[3])+min(a[1],a[2‌​],a[3],a[4])+min(a[2],a[3])+min(a[2],a[3],a[4])+min(a[3],a[4])</code></p>