Cho một dãy \(N\) số nguyên \(a_1, a_2, ... , a_N\) đôi một khác nhau.

Yêu cầu

Với mỗi \(k\) \((2 ≤ k ≤ N)\), xét mọi cặp \(i,j\) \((1 ≤ i < j ≤ k)\), hãy tìm giá trị nhỏ nhất của \(|a_i − a_j|\).

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(N\) \((1 ≤ N ≤ 10^5)\).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, ... , a_N\) \((|a_i| ≤ 10^9)\).

Output

In ra trên \(N − 1\) dòng, dòng thứ \(k\) \((2 ≤ k ≤ N)\) là giá trị \(|a_i − a_j|\) nhỏ nhất.

Example

Gợi ý: Sử dụng Set, mỗi lần thêm ai vào Set, ta tìm 2 phần tử đứng sát với ai bằng upper_bound. Bài toán này cần dùng 2 Set khác nhau, một cái sắp xếp tăng dần, một cái sắp xếp giảm dần.