xsquare-and-array-operations

Xsquare loves to play with arrays a lot. Today, he has an array A consisting of N distinct integers. He wants to perform following operation over his array A.
Select a pair of consecutive integers say (Ai,Ai+1) for some 1 ≤ i < N. Replace the selected pair of integers with the max(Ai,Ai+1).
Replace N with the new size of the array A.
Above operation incurs a cost of rupees max(Ai,Ai+1) to Xsquare.
As we can see after N-1 such operations, there is only 1 element left. Xsquare wants to know the most optimal transformation strategy to reduce the given array A to only 1 element. 

A transformation strategy is considered to be most optimal if it incurs minimum cost over all possible transformation strategies.

Input
First line of input contains a single integer T denoting the number of test cases. First line of each test case starts with an integer N denoting the size of the array A. Next line of input contains N space separated integers, where i^th element denotes the value Ai.

Output
For each test case, print the minimum cost required for the transformation.

Constraints
 1 ≤ T ≤ 10^5 

 2 ≤ N ≤ 10^5 

 1 ≤ Ai ≤ 10^9 

 sum of N over all test case does not exceed 5*10^5 

 SAMPLE INPUT
2
3
1 2 3
3
1 3 2

SAMPLE OUTPUT
5
6


Explanation

Testcase 1 : 
1. Initially A[] = {1,2,3}. During first operation, Xsquare selected A_1 and A_2. Cost of this operation is 2 i.e max(A_1,A_2) .
2. Now, A[]={2,3}. During second operation, Xsquare selected A_1 and A_2. Cost of this operation is 3 i.e max(A_1,A_2) .
This way Xsquare manages to transform the given array with minimum cost i.e 5.
Testcase 2 : 
1. Initially A[] = {1,3,2}. During first operation, Xsquare selected A_1 and A_2. Cost of this operation is 3 i.e max(A_1,A_2) .
2. Now, A[]={3,2}. During second operation, Xsquare selected A_1 and A_2. Cost of this operation is 3 i.e max(A_1,A_2) .
This way , Xsquare manages to transform the given array with minimum cost i.e 6.

Source: hackerearth | Difficulty: HARD
Tags: Segment trees revisited

Data structures

Range queries

Divide and conquer


Solutions:
def printEnergy(l):
	en = 0
	
	for i in range(0, len(l) - 1):
		en += max(l[i], l[i+1])
		
	print(en)


t = int(input())

for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	printEnergy(l)



test = input();
test = int(test);

for i in range(0, test):
	size = input();
	size = int(size);

	total = 0;
	temp_list = [];
	temp_list = input().split();
	temp_list = [int(j) for j in temp_list];

	if (temp_list[0] >= temp_list[1]):
		total = total + temp_list[0];
	if(temp_list[size-1] > temp_list[size-2]):
	   total = total + temp_list[size-1];
	for k in range(1,size-1):
		if (temp_list[k]>temp_list[k-1])|(temp_list[k]>=temp_list[k+1]):
			if (temp_list[k]>temp_list[k-1])&(temp_list[k]>=temp_list[k+1]):
				total = total + 2*temp_list[k];
			else:
				total = total + temp_list[k];

	print(total);