Після невдалого спілкування з дівчинкою Соньою хлопчик Халек вирішив взятися за голову і почати вчити програмування!

Він вирішив вивчити масиви і натрапив на таку задачу. Дано масив ~a~ з ~n~ цілих чисел. Для кожного префіксу масиву потрібно вивести значення ~max_i - min_i~, де ~max_i~ - це максимум на префіксі ~i~, а відповідно ~min_i~ - мінімум. Знайдіть таке значення для кожного ~i~ ~(1 \le i \le n)~.

Є одна проблемка, Халек ще не вчив ні цикли, ні іфи. Вам потрібно допомогти Халеку, щоб він не розчарувався в програмуванні, як в спілкуванні з дівчатами.

Input

В першому рядку задано одне ціле число ~n~ ~(1 \le n \le 10^6)~.

В наступному рядку задано масив ~a~ - ~n~ цілих чисел ~(-10^9\le a_i \le 10^9)~.

Output

Потрібно вивести через пробіл ~n~ цілих чисел - різницю максимуму і мінімуму на кожному з префіксів.

Sample Input 1

4
-1 3 4 10

Sample Output 1

0 4 5 11

Notes

Префікс - це підмасив, який починається з першого елементу. Тобто декілька елементів, які йдуть підряд з початку масиву.