CTDL - set10 - Hiệu hai phần tử

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 \le k \le N)\), xét mọi cặp \(i,j\) \((1 \le i < j \le 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 \le N \le 10^5)\).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, ... , a_N\) \((|a_i| \le 10^9)\).

Output

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

Example

6 
 1 5 12 8 10 2

4 
 4 
 3 
 2 
 1

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.