Masala #0322

Sizga N ta elementdan iborat A to’plam berilgan. Siz ko’pi bilan bir marotaba A to’plamning ixtiyoriy ikki elementini o’rnini almashtirishingiz mumkin. Natijaviy to’plamda to’plam unvoni max(A_i – A_j) ga teng. Bu yerda 1 < i ≤ N, j esa i dan kichik bo’lgan A_i > A_j shartni qanoatlantiruvchi eng katta indeks(agar bunday indeks mavjud bo’lmasa bu element to’plam unvonini hisoblashda ishlatilmaydi).

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 10) testlar soni kiritiladi.

Har bir testning birinchi satrida bitta butun son, N(2 ≤ N ≤ 10⁵) to’plam elementlari soni kiritiladi, ikkinchi satrida esa N ta butun son, A_i(1 ≤ A_i ≤ 10⁹) to’plam elementlari kiritiladi.

Chiqish faylida har bir test uchun alohida qatorda berilgan to’plamdan hosil qilish mumkin bo’lgan eng katta to’plam unvonini chop eting.