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\max_{\substack{1 \le j < i}}|a_i - a_j|\).

Đầu vào

Dòng đầu chứa số nguyên dương \(n\) \((2 \leq n \leq 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\%\) số test có \(n \le 1000\).

Ví dụ

Đầu vào:

5
1 9 -1 4 5

Đầu ra:

8 10 5 6