Unequal Goodness
42% Success733 Attempts30 Points4s Time Limit256MB Memory1024 KB Max Code

You are given an array \(A\) of \(N\) integers. A subarray from \(l\) to \(r\) \((l < r)\) is good if \(A[l] != A[r]\).

You have to find the \(maximum\) possible \(sum\) of elements of a good subarray. If there is no such good subarray then print "Not Possible".

Input Format:

  • The first line contains an integer \(T\), which denotes the number of test cases.
  • The first line of each test case contains \(N\).
  • The second line of each test case contains \(N\) space-separated integers, denoting the elements of array \(A\).

Output Format:

For each test case, print the maximum possible sum of elements of good subarray or print "Not Possible" (without double quotes) if there is no such good subarray.

Constraints:

\(1 \leq T \leq 10\)
\(2 \leq N \leq 2*10^5\)
\(-10^9 \leq A[i] \leq 10^9\)

Examples
Input
1
5
2 3 2 4 2
Output
11
Explanation

For test case \(1\): The given array is \([2 , 3 , 2 , 4 , 2]\), here maximum possible sum of elements of a good subarray is \(11\), which is from index \((1 , 4)\).

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results