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

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

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

Input Specification

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

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

Output Specification

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

Sample Input 1

4
-1 3 4 10

Sample Output 1

0 4 5 11