Welcome to Sillyville, a beautiful country where N states are arranged in a straight line and these states are getting ready for its presidential election on March 09, 2024. Only two candidates are participating in this election. Mr. Hero Harris is the current president and wants to become president again. In the other corner, Mr. Villain Victor is his opponent. In this presidential election. Each state will act like a battleground, and whoever wins in each state gets an important point known as the electoral vote. So, there are a total of N electoral votes and the candidate who gets more electoral votes will win the election.
Government secret agencies predict that Mr. Hero Harris is set to win or lose in the ith state by Xi votes (So, Xi positive means Hero Harris will win, Xi negative means Hero Harris will lose, and Xi = 0 indicates a tie, and in that case, no one will get the electoral vote ). To secure the biggest victory, Hero Harris aims to strategically merge some adjacent states (alter state borders). Mr. Hero Harris will win and get one electoral vote after merging states numbered from l to r if and only if $\sum\limits_{i=l}^r{X_i} > 0$.
The future of Sillyville rests in your hands! Your task is to figure out the optimal way to merge adjacent states (change state borders) so that Hero Harris can maximize the electoral vote difference against his opponent. More formally, your task is to maximize Electoral_VoteHeroHarris - Electoral_VoteVillainVictor.
Input
The first line contains an integer T (1 ≤ T ≤ 100), representing the number of test cases. Each test case contains two lines of input. The first line contains an integer N (2 ≤ N ≤ 105), representing the number of states in Sillyville. The second line contains N space-separated integers, representing the expected winning or losing margin Xi (-104 ≤ Xi ≤ 104 , Xi$\neq$0).
Input file is large. Please use faster input/output methods.
Output
For each test case, output a single line in the format “Case X: Y” where X is the case number and Y is the desired answer.
Sample
| Sample Input | Sample Output |
|---|---|
4 5 -3 4 1 2 3 5 -1 5 -10 6 -4 1 -6 2 5 -5 | Case 1: 4 Case 2: 1 Case 3: -1 Case 4: 0 |
Notes
Explanation
Case 1: Consider merging the first two states (-3 4) (1) (2) (3). Case 2: Consider merging first two and last two states (-1 5) (-10)( 6 -4)
Contest: NCPC 2023 Onsite Hosted by JU
Problem setter: Mohammad Ashraful Islam