Masala #UT4PSM4V6C

Xotira 512 MB Vaqt 3000 ms
14

Noto'g'ri yig'indi

Sobirjonda uzunligi \(n\) ga teng \(arr\) butun sonlar massivi bor. Sobirjon shunday ikkita \(i,j(i \neq j)\) sonlar olmoqchiki, \(arr[i] + arr[j]\) yig'indi maksimal bo'lsin.

Ammo muammo shundaki, Sobirjon qo'shish amalini xato bajaradi. U sonlarni qo'shganda xona ko'chisini inobatga olmaydi. Ya'ni qaysidir xonalar uchun, shu xonalardagi raqamlar yig'indisi 9 dan oshsa ham, 1 ni yodda saqlamaydi, keyingi razryadga ta'sir qildirmaydi. Aniq misollar bilan tushuntirgan quyroq.

5 + 5 = 0; 23+17 = 30; 354 + 168 = 412; 55 + 55 = 0; 9+11 = 10;

1000023 + 1070099 = 2070012; 12 + 7 = 19; 9 + 7 = 6; 124 + 123 = 247;


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 10)\) testlar soni kiritiladi.

Keyin har bir test uchun alohida, birinchi qatorda butun son - \(n(1 \leq n \leq 2 * 10^5)\) kitiriladi. Keyingi qatorda \(n\) ta butun son, \(arr\) massivi elementlar kiritiladi. Sonlar \(0..10^9\) oralig'ida ekanligi kafolatlanadi.

Barcha testlar kesimida \(n\) larning summasi \(10^6\) dan oshmasligi kafolatlanadi.


Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda, uchta butun son chiqaring:

maksimal \(arr[i] + arr[j]\) yig'indini, \(i\) va \(j\) ni. To'g'ri keluvchi \((i, j)\) lar juftligi bir nechta bo'lsa, oldin \(i\) ni minimallashtirishga harakat qiling, so'ngra \(j\) ni  minimallashtirishting. 


Misollar
# input.txt output.txt
1
3
3
12 9 7
2
55 55
4
155 55 955 555
19 1 3
0 1 2
900 2 3