663. Maximum Sum in a Circular Array

0

Medium

Given a circular array of integers called nums with a length of n, find the maximum possible sum of a non-empty subarray within nums.
A circular array means that the last element of nums is connected to the first element. In other words, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

Input Format

The first line of the input contains an integer t, which represents the number of test cases. Each test case is described by two lines. The first line contains an integer n, which is the size of the array nums. The second line contains n space-separated integers, representing the elements of nums.

Output Format

For each test case, print the maximum circular sum on a new line.

Example

Input

1
7
8 -8 9 -9 10 -11 12

Output

22

Constraints

1<=t<=100

1<=n<=1000

|A

1<=n<=1000

|A

_{i}| <= 10000Loading...

View Submissions

Console