অ্যারেম্যান একজন স্বনামধন্য মানুষ। তাঁর কাছে n টি পূর্ণসংখ্যার একটি অ্যারে আছে। তিনি অ্যারেটিকে কয়েকটি সাবঅ্যারেতে ভাগ করতে চান। প্রতিটি সাবঅ্যারের জন্য তাঁর ইউনিক সংখ্যাগুলোর যোগফলের সমান টাকা খরচ হবে। যেমনঃ যদি তাঁর অ্যারে হয় (2, 4 ,4, 6) এবং তিনি এভাবে ভাগ করেনঃ {2}, {4,4,6} তাহলে তাঁর খরচ হবে 2+4+6=12 টাকা। আবার যদি এভাবে ভাগ করেনঃ {2,4},{4, 6} তাহলে খরচ হবে 2+4+4+6=16 টাকা।তিনি অ্যারেটিকে যত ইচ্ছা ততগুলো সাবঅ্যারেতে ভাগ করতে পারেন।কিন্ত প্রতিটি সাবঅ্যারের গ.সা.গু 1 থেকে বড় হতে হবে।যেমনঃ তিনি {2,4,6} কে সাবঅ্যারে হিসেবে নিতে পারেন। কিন্ত {2,3,4} কে সাবঅ্যারে হিসেবে নিতে পারেন না, কেননা এক্ষেত্রে গ.সা.গু 1। সবথেকে কম কত টাকা খরচ করে তিনি কাজটি করতে পারেন?
Input
ইনপুট এর প্রথম লাইনে একটি পূর্ণসংখ্যা n (1<=n<=10^5) থাকবে। পরের লাইনে থাকবে n টি পূর্ণসংখ্যা ai (2<=ai<=10^6)। ai হচ্ছে অ্যারের i তম সংখ্যা।
Output
n টি লাইন প্রিন্ট করতে হবে। i তম লাইনে থাকবে যদি অ্যারেটি শুধুমাত্র প্রথম i টি সংখ্যা নিয়ে গঠিত হয় তার জন্য উত্তর।
Samples
| Input | Output |
|---|---|
4 2 3 3 4 | 2 5 5 9 |
| Input | Output |
|---|---|
4 2 3 4 5 | 2 5 9 14 |
