// C++ program to find sum of all minimum and maximum   // elements Of Sub-array Size k.   #include          using     namespace     std  ;   // Returns sum of min and max element of all subarrays   // of size k   int     SumOfKsubArray  (  int     arr  []     int     N       int     k  )   {      // To store final answer      int     sum     =     0  ;      // Find all subarray      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )     {      // To store length of subarray      int     length     =     0  ;      for     (  int     j     =     i  ;     j      <     N  ;     j  ++  )     {      // Increment the length      length  ++  ;      // When there is subarray of size k      if     (  length     ==     k  )     {      // To store maximum and minimum element      int     maxi     =     INT_MIN  ;      int     mini     =     INT_MAX  ;      for     (  int     m     =     i  ;     m      <=     j  ;     m  ++  )     {      // Find maximum and minimum element      maxi     =     max  (  maxi       arr  [  m  ]);      mini     =     min  (  mini       arr  [  m  ]);      }      // Add maximum and minimum element in sum      sum     +=     maxi     +     mini  ;      }      }      }      return     sum  ;   }   // Driver program to test above functions   int     main  ()   {      int     arr  []     =     {     2       5       -1       7       -3       -1       -2     };      int     N     =     sizeof  (  arr  )     /     sizeof  (  arr  [  0  ]);      int     k     =     4  ;      cout      < <     SumOfKsubArray  (  arr       N       k  );      return     0  ;   }   

   // Java program to find sum of all minimum and maximum   // elements Of Sub-array Size k.   import     java.util.Arrays  ;   class   GFG     {      // Returns sum of min and max element of all subarrays      // of size k      static     int     SumOfKsubArray  (  int  []     arr       int     N       int     k  )     {      // To store the final answer      int     sum     =     0  ;      // Find all subarrays      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )     {      // To store the length of the subarray      int     length     =     0  ;      for     (  int     j     =     i  ;     j      <     N  ;     j  ++  )     {      // Increment the length      length  ++  ;      // When there is a subarray of size k      if     (  length     ==     k  )     {      // To store the maximum and minimum element      int     maxi     =     Integer  .  MIN_VALUE  ;      int     mini     =     Integer  .  MAX_VALUE  ;      for     (  int     m     =     i  ;     m      <=     j  ;     m  ++  )     {      // Find the maximum and minimum element      maxi     =     Math  .  max  (  maxi       arr  [  m  ]  );      mini     =     Math  .  min  (  mini       arr  [  m  ]  );      }      // Add the maximum and minimum element to the sum      sum     +=     maxi     +     mini  ;      }      }      }      return     sum  ;      }      // Driver program to test above functions      public     static     void     main  (  String  []     args  )     {      int  []     arr     =     {  2       5       -  1       7       -  3       -  1       -  2  };      int     N     =     arr  .  length  ;      int     k     =     4  ;      System  .  out  .  println  (  SumOfKsubArray  (  arr       N       k  ));      }   }   //This code is contributed by Vishal Dhaygude   

   # Returns sum of min and max element of all subarrays   # of size k   def   sum_of_k_subarray  (  arr     N     k  ):   # To store final answer   sum   =   0   # Find all subarrays   for   i   in   range  (  N  ):   # To store length of subarray   length   =   0   for   j   in   range  (  i     N  ):   # Increment the length   length   +=   1   # When there is a subarray of size k   if   length   ==   k  :   # To store maximum and minimum element   maxi   =   float  (  '-inf'  )   mini   =   float  (  'inf'  )   for   m   in   range  (  i     j   +   1  ):   # Find maximum and minimum element   maxi   =   max  (  maxi     arr  [  m  ])   mini   =   min  (  mini     arr  [  m  ])   # Add maximum and minimum element to sum   sum   +=   maxi   +   mini   return   sum   # Driver program to test above function   def   main  ():   arr   =   [  2     5     -  1     7     -  3     -  1     -  2  ]   N   =   len  (  arr  )   k   =   4   print  (  sum_of_k_subarray  (  arr     N     k  ))   if   __name__   ==   '__main__'  :   main  ()   

   using     System  ;   class     Program     {      // Returns sum of min and max element of all subarrays      // of size k      static     int     SumOfKSubArray  (  int  []     arr       int     N       int     k  )      {      // To store the final answer      int     sum     =     0  ;      // Find all subarrays      for     (  int     i     =     0  ;     i      <     N  ;     i  ++  )     {      // To store the length of subarray      int     length     =     0  ;      for     (  int     j     =     i  ;     j      <     N  ;     j  ++  )     {      // Increment the length      length  ++  ;      // When there is a subarray of size k      if     (  length     ==     k  )     {      // To store the maximum and minimum      // element      int     maxi     =     int  .  MinValue  ;      int     mini     =     int  .  MaxValue  ;      for     (  int     m     =     i  ;     m      <=     j  ;     m  ++  )     {      // Find maximum and minimum element      maxi     =     Math  .  Max  (  maxi       arr  [  m  ]);      mini     =     Math  .  Min  (  mini       arr  [  m  ]);      }      // Add maximum and minimum element in      // sum      sum     +=     maxi     +     mini  ;      }      }      }      return     sum  ;      }      // Driver program to test above functions      static     void     Main  ()      {      int  []     arr     =     {     2       5       -  1       7       -  3       -  1       -  2     };      int     N     =     arr  .  Length  ;      int     k     =     4  ;      Console  .  WriteLine  (  SumOfKSubArray  (  arr       N       k  ));      }   }   

   // JavaScript program to find sum of all minimum and maximum   // elements of sub-array size k.   // Returns sum of min and max element of all subarrays   // of size k   function     SumOfKsubArray  (  arr       N       k  )     {      // To store final answer      let     sum     =     0  ;      // Find all subarray      for     (  let     i     =     0  ;     i      <     N  ;     i  ++  )     {      // To store length of subarray      let     length     =     0  ;      for     (  let     j     =     i  ;     j      <     N  ;     j  ++  )     {      // Increment the length      length  ++  ;      // When there is subarray of size k      if     (  length     ===     k  )     {      // To store maximum and minimum element      let     maxi     =     Number  .  MIN_SAFE_INTEGER  ;      let     mini     =     Number  .  MAX_SAFE_INTEGER  ;      for     (  let     m     =     i  ;     m      <=     j  ;     m  ++  )     {      // Find maximum and minimum element      maxi     =     Math  .  max  (  maxi       arr  [  m  ]);      mini     =     Math  .  min  (  mini       arr  [  m  ]);      }      // Add maximum and minimum element in sum      sum     +=     maxi     +     mini  ;      }      }      }      return     sum  ;   }   // Driver program to test above function   const     arr     =     [  2       5       -  1       7       -  3       -  1       -  2  ];   const     N     =     arr  .  length  ;   const     k     =     4  ;   console  .  log  (  SumOfKsubArray  (  arr       N       k  ));   

   // C++ program to find sum of all minimum and maximum   // elements Of Sub-array Size k.   #include          using     namespace     std  ;   // Returns sum of min and max element of all subarrays   // of size k   int     SumOfKsubArray  (  int     arr  []     int     n       int     k  )   {      int     sum     =     0  ;     // to store our final sum      // multiset because nos. could be repeated      // multiset pair is {numberindex}      multiset   <  pair   <  int       int  >     >     ms  ;      int     i     =     0  ;     // back pointer      int     j     =     0  ;     // front pointer      while     (  j      <     n     &&     i      <     n  )     {      ms  .  insert  (      {     arr  [  j  ]     j     });     // inserting {numberindex}      // front pointer - back pointer + 1 is for checking      // window size      int     windowSize     =     j     -     i     +     1  ;      // Once they become equal start what we need to do      if     (  windowSize     ==     k  )     {      // extracting first since set is always in      // sorted ascending order      int     mini     =     ms  .  begin  ()  ->  first  ;      // extracting last element aka beginning from      // last (numbers extraction)      int     maxi     =     ms  .  rbegin  ()  ->  first  ;      // adding summation of maximum & minimum element      // of each subarray of k into final sum      sum     +=     (  maxi     +     mini  );      // erasing the ith index element from set as it      // won't appaer in next window of size k      ms  .  erase  ({     arr  [  i  ]     i     });      // increasing back pointer for next window of      // size k;      i  ++  ;      }      j  ++  ;     // always increments front pointer      }      return     sum  ;   }   // Driver program to test above functions   int     main  ()   {      int     arr  []     =     {     2       5       -1       7       -3       -1       -2     };      int     n     =     sizeof  (  arr  )     /     sizeof  (  arr  [  0  ]);      int     k     =     4  ;      cout      < <     SumOfKsubArray  (  arr       n       k  );      return     0  ;   }   

   // C++ program to find sum of all minimum and maximum   // elements Of Sub-array Size k.   #include       using     namespace     std  ;   // Returns sum of min and max element of all subarrays   // of size k   int     SumOfKsubArray  (  int     arr  []          int     n          int     k  )   {      int     sum     =     0  ;     // Initialize result      // The queue will store indexes of useful elements      // in every window      // In deque 'G' we maintain decreasing order of      // values from front to rear      // In deque 'S' we maintain increasing order of      // values from front to rear      deque   <     int     >     S  (  k  )     G  (  k  );      // Process first window of size K      int     i     =     0  ;      for     (  i     =     0  ;     i      <     k  ;     i  ++  )      {      // Remove all previous greater elements      // that are useless.      while     (     (  !  S  .  empty  ())     &&     arr  [  S  .  back  ()]     >=     arr  [  i  ])      S  .  pop_back  ();     // Remove from rear      // Remove all previous smaller that are elements      // are useless.      while     (     (  !  G  .  empty  ())     &&     arr  [  G  .  back  ()]      <=     arr  [  i  ])      G  .  pop_back  ();     // Remove from rear      // Add current element at rear of both deque      G  .  push_back  (  i  );      S  .  push_back  (  i  );      }      // Process rest of the Array elements      for     (     ;     i      <     n  ;     i  ++     )      {      // Element at the front of the deque 'G' & 'S'      // is the largest and smallest      // element of previous window respectively      sum     +=     arr  [  S  .  front  ()]     +     arr  [  G  .  front  ()];      // Remove all elements which are out of this      // window      if     (     !  S  .  empty  ()     &&     S  .  front  ()     ==     i     -     k  )      S  .  pop_front  ();      if     (     !  G  .  empty  ()     &&     G  .  front  ()     ==     i     -     k  )      G  .  pop_front  ();      // remove all previous greater element that are      // useless      while     (     (  !  S  .  empty  ())     &&     arr  [  S  .  back  ()]     >=     arr  [  i  ])      S  .  pop_back  ();     // Remove from rear      // remove all previous smaller that are elements      // are useless      while     (     (  !  G  .  empty  ())     &&     arr  [  G  .  back  ()]      <=     arr  [  i  ])      G  .  pop_back  ();     // Remove from rear      // Add current element at rear of both deque      G  .  push_back  (  i  );      S  .  push_back  (  i  );      }      // Sum of minimum and maximum element of last window      sum     +=     arr  [  S  .  front  ()]     +     arr  [  G  .  front  ()];      return     sum  ;   }   // Driver program to test above functions   int     main  ()   {      int     arr  []     =     {  2       5       -1       7       -3       -1       -2  }     ;      int     n     =     sizeof  (  arr  )  /  sizeof  (  arr  [  0  ]);      int     k     =     4  ;      cout      < <     SumOfKsubArray  (  arr       n       k  )     ;      return     0  ;   }   

   // Java program to find sum of all minimum and maximum    // elements Of Sub-array Size k.    import     java.util.Deque  ;   import     java.util.LinkedList  ;   public     class   Geeks     {      // Returns sum of min and max element of all subarrays       // of size k       public     static     int     SumOfKsubArray  (  int     arr  []          int     k  )         {         int     sum     =     0  ;     // Initialize result           // The queue will store indexes of useful elements       // in every window       // In deque 'G' we maintain decreasing order of       // values from front to rear       // In deque 'S' we maintain increasing order of       // values from front to rear       Deque   <  Integer  >     S  =  new     LinkedList   <>  ()  G  =  new     LinkedList   <>  ();      // Process first window of size K       int     i     =     0  ;         for     (  i     =     0  ;     i      <     k  ;     i  ++  )         {         // Remove all previous greater elements       // that are useless.       while     (     !  S  .  isEmpty  ()     &&     arr  [  S  .  peekLast  ()  ]     >=     arr  [  i  ]  )         S  .  removeLast  ();     // Remove from rear           // Remove all previous smaller that are elements       // are useless.       while     (     !  G  .  isEmpty  ()     &&     arr  [  G  .  peekLast  ()  ]      <=     arr  [  i  ]  )         G  .  removeLast  ();     // Remove from rear           // Add current element at rear of both deque       G  .  addLast  (  i  );         S  .  addLast  (  i  );         }             // Process rest of the Array elements       for     (     ;     i      <     arr  .  length  ;     i  ++     )         {         // Element at the front of the deque 'G' & 'S'       // is the largest and smallest       // element of previous window respectively       sum     +=     arr  [  S  .  peekFirst  ()  ]     +     arr  [  G  .  peekFirst  ()  ]  ;             // Remove all elements which are out of this       // window       while     (     !  S  .  isEmpty  ()     &&     S  .  peekFirst  ()      <=     i     -     k  )         S  .  removeFirst  ();         while     (     !  G  .  isEmpty  ()     &&     G  .  peekFirst  ()      <=     i     -     k  )         G  .  removeFirst  ();             // remove all previous greater element that are       // useless       while     (     !  S  .  isEmpty  ()     &&     arr  [  S  .  peekLast  ()  ]     >=     arr  [  i  ]  )         S  .  removeLast  ();     // Remove from rear           // remove all previous smaller that are elements       // are useless       while     (     !  G  .  isEmpty  ()     &&     arr  [  G  .  peekLast  ()  ]      <=     arr  [  i  ]  )         G  .  removeLast  ();     // Remove from rear           // Add current element at rear of both deque       G  .  addLast  (  i  );         S  .  addLast  (  i  );         }             // Sum of minimum and maximum element of last window       sum     +=     arr  [  S  .  peekFirst  ()  ]     +     arr  [  G  .  peekFirst  ()  ]  ;             return     sum  ;         }         public     static     void     main  (  String     args  []  )         {      int     arr  []     =     {  2       5       -  1       7       -  3       -  1       -  2  }     ;         int     k     =     4  ;         System  .  out  .  println  (  SumOfKsubArray  (  arr       k  ));      }   }   //This code is contributed by Gaurav Tiwari   

   # Python3 program to find Sum of all minimum and maximum    # elements Of Sub-array Size k.   from   collections   import   deque   # Returns Sum of min and max element of all subarrays   # of size k   def   SumOfKsubArray  (  arr     n      k  ):   Sum   =   0   # Initialize result   # The queue will store indexes of useful elements   # in every window   # In deque 'G' we maintain decreasing order of   # values from front to rear   # In deque 'S' we maintain increasing order of   # values from front to rear   S   =   deque  ()   G   =   deque  ()   # Process first window of size K   for   i   in   range  (  k  ):   # Remove all previous greater elements   # that are useless.   while   (   len  (  S  )   >   0   and   arr  [  S  [  -  1  ]]   >=   arr  [  i  ]):   S  .  pop  ()   # Remove from rear   # Remove all previous smaller that are elements   # are useless.   while   (   len  (  G  )   >   0   and   arr  [  G  [  -  1  ]]    <=   arr  [  i  ]):   G  .  pop  ()   # Remove from rear   # Add current element at rear of both deque   G  .  append  (  i  )   S  .  append  (  i  )   # Process rest of the Array elements   for   i   in   range  (  k     n  ):   # Element at the front of the deque 'G' & 'S'   # is the largest and smallest   # element of previous window respectively   Sum   +=   arr  [  S  [  0  ]]   +   arr  [  G  [  0  ]]   # Remove all elements which are out of this   # window   while   (   len  (  S  )   >   0   and   S  [  0  ]    <=   i   -   k  ):   S  .  popleft  ()   while   (   len  (  G  )   >   0   and   G  [  0  ]    <=   i   -   k  ):   G  .  popleft  ()   # remove all previous greater element that are   # useless   while   (   len  (  S  )   >   0   and   arr  [  S  [  -  1  ]]   >=   arr  [  i  ]):   S  .  pop  ()   # Remove from rear   # remove all previous smaller that are elements   # are useless   while   (   len  (  G  )   >   0   and   arr  [  G  [  -  1  ]]    <=   arr  [  i  ]):   G  .  pop  ()   # Remove from rear   # Add current element at rear of both deque   G  .  append  (  i  )   S  .  append  (  i  )   # Sum of minimum and maximum element of last window   Sum   +=   arr  [  S  [  0  ]]   +   arr  [  G  [  0  ]]   return   Sum   # Driver program to test above functions   arr  =  [  2     5     -  1     7     -  3     -  1     -  2  ]   n   =   len  (  arr  )   k   =   4   print  (  SumOfKsubArray  (  arr     n     k  ))   # This code is contributed by mohit kumar   

   // C# program to find sum of all minimum and maximum    // elements Of Sub-array Size k.    using     System  ;   using     System.Collections.Generic  ;   class     Geeks   {      // Returns sum of min and max element of all subarrays       // of size k       public     static     int     SumOfKsubArray  (  int     []  arr          int     k  )         {         int     sum     =     0  ;     // Initialize result       // The queue will store indexes of useful elements       // in every window       // In deque 'G' we maintain decreasing order of       // values from front to rear       // In deque 'S' we maintain increasing order of       // values from front to rear       List   <  int  >     S     =     new     List   <  int  >  ();      List   <  int  >     G     =     new     List   <  int  >  ();      // Process first window of size K       int     i     =     0  ;         for     (  i     =     0  ;     i      <     k  ;     i  ++  )         {         // Remove all previous greater elements       // that are useless.       while     (     S  .  Count     !=     0     &&     arr  [  S  [  S  .  Count     -     1  ]]     >=     arr  [  i  ])         S  .  RemoveAt  (  S  .  Count     -     1  );     // Remove from rear       // Remove all previous smaller that are elements       // are useless.       while     (     G  .  Count     !=     0     &&     arr  [  G  [  G  .  Count     -     1  ]]      <=     arr  [  i  ])         G  .  RemoveAt  (  G  .  Count     -     1  );     // Remove from rear       // Add current element at rear of both deque       G  .  Add  (  i  );         S  .  Add  (  i  );         }         // Process rest of the Array elements       for     (     ;     i      <     arr  .  Length  ;     i  ++     )         {         // Element at the front of the deque 'G' & 'S'       // is the largest and smallest       // element of previous window respectively       sum     +=     arr  [  S  [  0  ]]     +     arr  [  G  [  0  ]];         // Remove all elements which are out of this       // window       while     (     S  .  Count     !=     0     &&     S  [  0  ]      <=     i     -     k  )         S  .  RemoveAt  (  0  );         while     (     G  .  Count     !=     0     &&     G  [  0  ]      <=     i     -     k  )         G  .  RemoveAt  (  0  );         // remove all previous greater element that are       // useless       while     (     S  .  Count     !=     0     &&     arr  [  S  [  S  .  Count  -  1  ]]     >=     arr  [  i  ])         S  .  RemoveAt  (  S  .  Count     -     1     );     // Remove from rear       // remove all previous smaller that are elements       // are useless       while     (     G  .  Count     !=     0     &&     arr  [  G  [  G  .  Count     -     1  ]]      <=     arr  [  i  ])         G  .  RemoveAt  (  G  .  Count     -     1  );     // Remove from rear       // Add current element at rear of both deque       G  .  Add  (  i  );         S  .  Add  (  i  );         }         // Sum of minimum and maximum element of last window       sum     +=     arr  [  S  [  0  ]]     +     arr  [  G  [  0  ]];         return     sum  ;         }         // Driver code      public     static     void     Main  (  String     []  args  )         {      int     []  arr     =     {  2       5       -  1       7       -  3       -  1       -  2  }     ;         int     k     =     4  ;         Console  .  WriteLine  (  SumOfKsubArray  (  arr       k  ));      }   }   // This code is contributed by gauravrajput1    

   // JavaScript program to find sum of all minimum and maximum   // elements Of Sub-array Size k.   // Returns sum of min and max element of all subarrays   // of size k   function     SumOfKsubArray  (  arr          k  )   {      let     sum     =     0  ;     // Initialize result      // The queue will store indexes of useful elements      // in every window      // In deque 'G' we maintain decreasing order of      // values from front to rear      // In deque 'S' we maintain increasing order of      // values from front to rear      let     S     =     [];      let     G     =     [];      // Process first window of size K      let     i     =     0  ;      for     (  i     =     0  ;     i      <     k  ;     i  ++  )      {      // Remove all previous greater elements      // that are useless.      while     (     S  .  length     !=     0     &&     arr  [  S  [  S  .  length     -     1  ]]     >=     arr  [  i  ])      S  .  pop  ();     // Remove from rear      // Remove all previous smaller that are elements      // are useless.      while     (     G  .  length     !=     0     &&     arr  [  G  [  G  .  length     -     1  ]]      <=     arr  [  i  ])      G  .  pop  ();     // Remove from rear      // Add current element at rear of both deque      G  .  push  (  i  );      S  .  push  (  i  );      }      // Process rest of the Array elements      for     (     ;     i      <     arr  .  length  ;     i  ++     )      {      // Element at the front of the deque 'G' & 'S'      // is the largest and smallest      // element of previous window respectively      sum     +=     arr  [  S  [  0  ]]     +     arr  [  G  [  0  ]];      // Remove all elements which are out of this      // window      while     (     S  .  length     !=     0     &&     S  [  0  ]      <=     i     -     k  )      S  .  shift  (  0  );      while     (     G  .  length     !=     0     &&     G  [  0  ]      <=     i     -     k  )      G  .  shift  (  0  );      // remove all previous greater element that are      // useless      while     (     S  .  length     !=     0     &&     arr  [  S  [  S  .  length  -  1  ]]     >=     arr  [  i  ])      S  .  pop  ();     // Remove from rear      // remove all previous smaller that are elements      // are useless      while     (     G  .  length     !=     0     &&     arr  [  G  [  G  .  length     -     1  ]]      <=     arr  [  i  ])      G  .  pop  ();     // Remove from rear      // Add current element at rear of both deque      G  .  push  (  i  );      S  .  push  (  i  );      }      // Sum of minimum and maximum element of last window      sum     +=     arr  [  S  [  0  ]]     +     arr  [  G  [  0  ]];      return     sum  ;   }   // Driver code      let     arr     =     [  2       5       -  1       7       -  3       -  1       -  2  ];      let     k     =     4  ;      console  .  log  (  SumOfKsubArray  (  arr       k  ));   // This code is contributed by _saurabh_jaiswal