Khi Majin Buu - một mối nguy hại lớn được giải phong ấn, các chiến binh Z phải chọn ra những chiến binh mạnh nhất để đồng hành cùng bảo vệ Trái Đất.

Họ tìm được \(N\) chiến binh, sức mạnh của người thứ \(i\) \((1 \leq i \leq N)\) là \(p_i\). Bởi vì thời gian là có hạn nên team Z muốn tìm ra một chiến binh có đủ sức mạnh càng sớm càng tốt. Họ có một kĩ thuật ít người biết là Fusion Dance - kĩ thuật cho phép từ hai người có cùng sức mạnh tạo ra được một chiến binh mới có chỉ số sức mạnh bằng tổng sức mạnh của hai người đó, tức là nếu hai người thứ \(i\) và \(j\) \((i \neq j)\) có \(p_i = p_j\) thì hai người này có khả năng hợp thể thành một người mới có chỉ số sức mạnh bằng \((p_i + p_j)\). Người được tạo thành từ phép hợp thể vừa nếu vẫn có thể tiếp tục hợp thể với các người khác miễn là thỏa mãn điều kiện sức mạnh bằng nhau.

Yêu cầu: Với mỗi \(x\) từ \(1\) đến \(N\), hãy giúp team Z tìm ra cách tạo ra chiến binh có chỉ số sức mạnh lớn nhất từ \(x\) chiến binh đầu tiên.

Input

• Dòng đầu tiên gồm một số nguyên dương \(N\) \((1 \leq N \leq 5 \times 10^5)\) là số chiến binh
• Dòng tiếp theo gồm \(N\) số nguyên dương, số thứ \(i\) \((1 \leq i \leq N)\) là \(p_i\) \((1 \leq p_i \leq 10^6)\) - sức mạnh của chiến binh thứ \(i\).

Output

• Một dòng duy nhất gồm \(N\) số nguyên dương, số thứ \(x\) \((1 \leq x \leq N)\) là chỉ số sức mạnh lớn nhất có thể có được từ \(x\) chiến binh đầu tiên

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \leq 100\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 1000\).
• Subtask \(4\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
3 2 4 1 2

3 3 4 4 8