У нас є ~N~ діжок різної висоти. В ~i~-у діжку неможливо налити більше води, ніж її висота. Нам треба заповнити діжки таким чином, щоб висота води в (~i+1~)-й діжці була на ~K~ більше, ніж висота води, яку залили в ~i~-у діжку, для ~1 \le i \le N-1~.

Необхідно знайти максимально можливе значення ~K~ і максимальну початкову висоту води ~H~.

Якщо ~N~ = 1, то потрібно заповнити цей контейнер до верху, а значення ~K~ буде ~H_1-1~.

В загальному випадку перший контейнер повинен бути заповнений принаймні до висоти 1.

Формат вхідних даних

Перший рядок містить кількість тестів ~T~ (~1 \le T \le 10^5~).

Далі йдуть тести у такому форматі:

Перший рядок кожного тесту - N (~1 \le N \le 10^5~) - кількість наявних діжок.

Другий рядок тесту містить ~N~ цілих чисел, розділених пропуском ~H_i~ (~1 \le H_i \le 10^{12}~) - висоти відповідних діжок.

В одному тесті кількість всіх чисел не перевищує ~10^5~.

Формат вихідних даних

Для кожного тесту в окремому рядку вивести через пропуск ~K~ та ~H~

Примітка

Для першого тесту оптимальне наповнення діжок буде при максимальному K = 49 і максимальній висоті 2. Наповнення діжок буде таким: 2, 51, 100.

У другому тесті маємо лише одну діжку, тому максимальне значення K = 7, а максимальна початкова висота рівна 8.

Приклад вхідних даних

2
3
200 150 100
1
8

Приклад вихідних даних

49 2
7 8