У мальчика Саши есть массив \(a\) из \(n\) целых чисел. Ему стало скучно, и для всех \(i\), \(j\) (\(i < j\)) он записал минимальное значение из \(a_i\) и \(a_j\). Он получил новый массив \(b\) размером \(\frac{n\cdot (n-1)}{2}\).
Например, если \(a=\) [\(2,3,5,1\)], он запишет [\(\min(2, 3), \min(2, 5), \min(2, 1), \min(3, 5), \min(3, 1), min(5, 1)\)] \(=\) [\(2, 2, 1, 3, 1, 1\)].
Также, он случайным образом перемешал все элементы массива \(b\).
К сожалению, он забыл массив \(a\), и ваша задача — восстановить любой возможный массив \(a\), из которого мог быть получен массив \(b\).
Элементы массива \(a\) должны находиться в диапазоне \([-10^9,10^9]\).
Примечание
В первом примере Саша выбрал массив \([1,3,3]\), тогда массив \(b\) будет выглядеть как \([\min(a_1,a_2)=1, \min(a_1,a_3)=1, \min(a_2,a_3)=3]\), после перемешивания его элементов, массив может выглядеть как \([1,3,1]\).
Во втором примере есть только одна пара, поэтому подходит массив \([10,10]\). Другим подходящим массивом может быть \([15,10]\).