Quang đang sử dụng những con búp bê để dạy một số trẻ về các đồ vật có kích thước khác nhau. Những con búp bê này rỗng bên trong nên những con búp bê nhỏ hơn có thể được đặt bên trong những con búp bê lớn hơn.

Mỗi con búp bê có một kích thước nhật định. Một con búp bê có kích thước \(x\) có thể nằm gọn trong một con búp bê khác có kích thước \(y\) nếu \(y-x>=2\).

Một chồng búp bê được hình thành bằng cách chọn một số búp bê mà Quang có và liên tục lắp con búp bê nhỏ nhất vào con búp bê nhỏ thứ hai cho đến khi còn lại một con búp bê. Kích thước của chồng búp bê là số lượng búp bê được sử dụng để tạo ra nó.

Có \(n\) ngày. Vào ngày thứ \(i(1 ≤ i ≤ n), Quang sẽ mua một con búp bê có kích thước \)a_i~. Sau khi mua búp bê, anh ta cố gắng xây dựng một chồng búp bê với số lượng búp bê tối đa.

Yêu cầu: Hãy giúp Quang tính toán với mỗi ngày kích thước tối đa của chồng búp bê bằng cách sử dụng những con búp bê có sẵn trong ngày đó.

Input

• Dòng đầu chứa đúng một số nguyên \(n\) (\(n ≤ 10^5\)).
• • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) (\(a_i ≤ 5*10^5\)), với \(a_i\) đại diện cho kích thước của những búp bê được mua vào mỗi ngày trong số \(n\) ngày.
• ## Output
• Ghi ra \(n\) số nguyên trên một dòng duy nhất cách nhau bới dấu cách, số nguyên thứ \(i\) là kích thước tối đa của chồng búp bê sử dụng số búp bê có sẵn trong ngày đó