Độ tốt không đều

Trong một lần tham quan xưởng gốm, FullHouse Dev được thợ gốm giao cho một thử thách thú vị. Họ phải tìm ra đoạn gốm có tổng giá trị cao nhất, với điều kiện đặc biệt về độ tốt của đoạn gốm đó.

Bài toán

FullHouse Dev nhận được một dãy \(n\) mảnh gốm, mỗi mảnh có một giá trị nguyên. Một đoạn gốm từ vị trí \(l\) đến \(r\) được gọi là tốt nếu \(A[l] = A[r]\). Nhiệm vụ của nhóm là tìm ra tổng giá trị lớn nhất có thể của một đoạn gốm tốt. Nếu không tìm được đoạn gốm nào thỏa mãn, in ra "Not Possible".

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Dòng đầu tiên của mỗi test case chứa số nguyên \(n\).
• Dòng thứ hai của mỗi test case chứa \(n\) số nguyên, biểu thị giá trị của từng mảnh gốm trong dãy \(A\).

OUTPUT FORMAT:

• Với mỗi test case, in ra tổng giá trị lớn nhất có thể của một đoạn gốm tốt, hoặc in "Not Possible" nếu không tìm được đoạn gốm nào thỏa mãn.

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

1
5
2 3 2 4 2

OUTPUT

13

Giải thích

Ở test case này, dãy gốm có giá trị là \([2, 3, 2, 4, 2]\). Đoạn gốm có tổng giá trị lớn nhất thỏa mãn điều kiện là đoạn từ vị trí 1 đến 5, với tổng giá trị là \(2 + 3 + 2 + 4 + 2 = 13\). Đoạn này thỏa mãn vì phần tử đầu và cuối đều bằng 2.