Cheapest Subarray

3.5

27 votes
Arrays, Basic Programming, Basics of Implementation, Easy, Implementation, Looping statement
Problem

Visuals can be deceptive, and so can be the titles of the contest, but not every time you'll be asked tough questions in an EASY contest.

In this problem, you will be given an array of integers and you need to tell the cost of the cheapest possible subarray of length at least two.

A subarray is the sequence of consecutive elements of the array and the cost of a subarray is the sum of minimum and the maximum value in the subarray. 

Note: In an array of length n, there are n(n1)2 subarrays whose length is atleast 2.

Constraints:

  • 1t10
  • 2n2×104
  • 1ai2×104

Input Format:

The first line contains a single integer t  denoting the number of test cases.

The first line of each test case contains n  i.e the number of elements in the array. Next lines contains n  space-separated integers ai

Output Format:

Print t lines each containing a single integer. ith integer denotes the cost of the cheapest subarray for the ith array.

Sample Input
2
2
3 2
3
3 4 2
Sample Output
5
6
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • The only possible subarray of length atleast 2 is [3, 2], Its cost is minimum + maximum = 2 + 3 = 5;
  • Three subarrays of lengths at least 2 are possible i.e. [3, 4], [4, 2] and [3, 4, 2]. The minimum possible cost is 6 for the subarrays [4, 2] and [3, 4, 2]
Editor Image

?