Nhà

Chính quyền thành phố muốn xây dựng nhà trên một khu phố. Ở mỗi thời điểm, sẽ có một ngôi nhà được xây hoặc được phá bỏ ở một vị trí nhất định. Sau khi mỗi ngôi nhà được xây dựng hoặc phá bỏ, nếu trên khu phố có ít nhất hai ngôi nhà, chính quyền muốn tìm ra khoảng cách nhỏ nhất giữa hai ngôi nhà khác nhau bất kì.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)) là số lượng lần xây dựng/phá bỏ nhà.

• \(n\) dòng tiếp theo, mỗi dòng gồm một số nguyên \(p\) (\(1 \le p \le 10^9\)) là một vị trí. Nếu hiện tại chưa có ngôi nhà nào ở vị trí \(p\) thì xây dựng một ngôi nhà ở đây, ngược lại phá bỏ ngôi nhà này.

Output

In ra \(n\) dòng, sau mỗi lần xây dựng/phá bỏ nhà hãy in ra khoảng cách nhỏ nhất giữa hai ngôi nhà. Nếu không tồn tại ít nhất hai căn nhà, in ra \(-1\).

Example

Input:

5
1
3
2
2
3

Output:

-1
2
1
2
-1