Cho một dãy số nguyên A gồm n phần tử, chúng ta định nghĩa 2 loại dãy con của A như sau:

• Subarr: dãy con gồm các phần tử liên tiếp của A.
• Subseq: dãy con gồm một tập các phần tử của A.

Cho dãy A, tính Subarr không rỗng và Subseq không rỗng có tổng lớn nhất.

• Dòng đâu chứa số nguyên dương t là số bộ test.
• t cặp dòng tiếp theo, dòng đầu chứa số nguyên n, dòng 2 chứa dãy A.

• In ra tt dòng, mỗi dòng gồm 2 số theo thứ tư max Subarr, max Subseq

• 1≤t≤10
• 1≤n≤100000
• 0≤|a_i|≤100000