# First and Last solution codechef

## First and Last solution codechef

You are given an array A=[A1,A2,,AN] of length N.

You can right rotate it any number of times (possibly, zero). What is the maximum value of A1+AN you can get?

Note: Right rotating the array [A1,A2,,AN] once gives the array [AN,A1,A2,,AN1]. For example, right rotating [1,2,3] once gives [3,1,2], and right rotating it again gives [2,3,1].

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases. The description of the test cases follows.
• The first line of each test case contains a single integer N, denoting the length of array A.
• The second line of each test case contains N space-separated integers A1,A2,,AN — denoting the array A.

## First and Last solution codechef

### Output Format

For each test case, output on a new line the maximum value of A1+AN you can get after several right rotations.

### Constraints

• 1T1000
• 2N105
• 1Ai109
• The sum of N across all test cases does not exceed 105

### Sample Input 1

3
2
5 8
3
5 10 15
4
4 4 4 4


### Sample Output 1

13
25
8


## First and Last solution codechef

Test case 1: Whether you right rotate the array or not, you will always end up with A1+AN=13.

Test case 2: It is optimal to right rotate the array once after which the array becomes [15,5,10] with A1+AN=25.

Test case 3: No matter how much you right rotate the array, you will always obtain A1+AN=8.