Cho dãy số có $n$ phần tử $a_1,a_2,...,a_n$. Với mỗi $i$ chạy từ $2$ tới $n$, bạn hãy tìm khoảng cách lớn nhất của $a_i$ với các phần tử đứng trước - nói cách khác với mỗi $i$ bạn hãy xác định giá trị biểu thức ${\displaystyle \underset{\begin{array}{c}1\le j<i\end{array}}{max}|a_i-a_j|}$.

Đầu vào

Dòng đầu chứa số nguyên dương $n$ $(2\le n\le {10}^5)$ là số phần tử của dãy.

Dòng tiếp theo gồm $n$ số nguyên là các phần tử của dãy có giá trị tuyệt đối không vượt quá ${10}^9$.

Đầu ra

Một dòng duy nhất chứa $n-1$ số tự nhiên.

Subtask

$30\mathrm{\%}$ số test có $n\le 1000$.

Ví dụ

Đầu vào:

5
1 9 -1 4 5

Đầu ra:

8 10 5 6