Шинэ жилийн баяраар n хүүхэд дараалан зогсож байна. i-р хүүхдийн "сайхан байдлийн түвшин" нь \(a_i\) юм. Санта хүүхэд бүрийг "сайн жагсаалт" эсвэл "муу жагсаалт"-д оруулах шийдвэр гарган ажиллаж буй юм.

X гэсэн бүхэл тоо эхлээд 0 байна. Санта яг n-1 удаа дараах үйлдлийг гүйцэтгэж муу болон сайн жагсаалтыг үүсгэх юм:

• Дараалалд байгаа нэгдүгээр эсвэл хоёрдугаар хүүхдийг сонгож дарааллаас хасах юм.
• w нь сонгогдсон хүүхдийн сайн байдлийн түвшин байг.
• Хэрэв нэгдүгээр хүүхдийг сонгосон бол түүнийг сайн жагсаалтад нэмж, X-д w-г нэмнэ.
• Хэрэв хоёрдугаар хүүхдийг сонгосон бол түүнийг муу жагсаалтад нэмж, X-ээс w-г хасна.

Бүх үйлдлийн дараа яг нэг хүүхэд жагсаалтад ороогүй үлдэнэ.

Санта n-1 үйлдлийн дараа олж чадах X-ийн хамгийн их утгыг тодорхойл.

Оролт:

Эхний мөрөнд тестийн тоо болох t өгөгдөнө

Тест бүр дараах хэлбэрээр өгөгдөнө

n
a1 a2 a3 a4 ... an

Гаралт:

Тохиолдол (Тест) бүрт Сантагийн олж чадах X-ийн хамгийн их утгыг нэг бүхэл тоогоор хэвлэ.

Хязгаарлалтууд:

• \(1 <= t <= 10^4\)
• \(2 <= N <= 2*10^5\)
• \(-10^9 <= aᵢ <= 10^9\)

Дэд бодлого

Жишээ:

Оролт-1

7
2
2 -3
4
1 4 3 4
4
-4 2 3 -6
5
-2 -3 4 10 -9
5
-12345678 -1000000000 -999999999 1000000000 -999999999
2
-7 1
5
7 -6 -1 -8 -8

Гаралт-1

8
4
15
2987654321
-1
29

Тайлбар

Эхний тохиолдолд Санта яг нэг үйлдэл хийнэ. Хэрэв нэгдүгээр хүүхдийг сонговол a1=2-ийг X-д нэмж X=2 болно; хэрэв хоёрдугаар хүүхдийг сонговол a2=-3-ийг X-ээс хасч X=3 болно. Тиймээс хариулт нь 3 юм.

Хоёрдугаар тохиолдолд хийх гурван үйлдэл бүрт нэгдүгээр хүүхдийг сонгох нь оновчтой. X-ийн утга 1+4+3=8 болно.

Гуравдугаар тохиолдол

Анх : -4 2 3 -6 Нэгдүгээр хүүхдийг сонгосны дараа : 2 3 -6 X = 0 - 4 = -4 болно Дахин нэгдүгээр хүүхдийг сонгож : 3 -6 X = -4 + 2 = -2 Харин одоо хоёр дахь хүүхдийг сонгоход : 3 X = -2 - (-6) = 4