يقوم نادي جري بتجنيد أعضاء وينمو بسرعة، حيث ينضم عضو جديد واحد بالضبط كل يوم. يأتي كل عضو بمستوى مهارة أولي محدد، ويُعطى معرفاً فريداً (ID) بناءً على ترتيب وصوله.

في نهاية كل يوم، يحب المدرب حساب مقياس يسميه "إجمالي الإمكانات" للنادي. هذه القيمة هي ببساطة مجموع الإمكانات الفردية لجميع الأعضاء الحاليين. للحفاظ على حماس الأعضاء، يتم حساب إمكانات العضو من خلال سيناريو افتراضي يتضمن تمريناً واحداً مكثفاً.

في هذا التمرين التخيلي، يمكن للعضو اختيار بذل قدر معين من الجهد لرفع مستوى مهارته مؤقتاً. مقابل كل $1$ وحدة جهد يبذلها، يزداد مستوى مهارته بمقدار $1$ وحدة بالضبط. وفي المقابل، يكسب $1$ وحدة من "السعادة" عن كل عضو آخر موجود حالياً في النادي يحقق الشرطين التاليين:

• انضم إلى النادي بعده بشكل صارم؛ و
• كان في الأصل أكثر مهارة منه بشكل صارم، ولكن تم اللحاق به أو تجاوزه الآن بفضل التمرين.

لاحظ أنه خلال هذا الحساب، يزداد فقط مستوى مهارة ذلك العضو، بينما تظل مستويات مهارة جميع الأعضاء الآخرين ثابتة عند قيمها الأصلية.

تُعرَّف إمكانات العضو الواحد بأنها أقصى قيمة ممكنة لمكسبه الصافي (السعادة ناقص الجهد) التي يمكنه تحقيقها من خلال اختيار مستوى جهده بشكل أمثل. هذه التمارين نظرية تماماً؛ فهي تُستخدم فقط لتقرير المدرب اليومي، وتظل مستويات المهارة الفعلية للأعضاء دون تغيير من يوم لآخر.

مهمتك هي مساعدة المدرب في حساب إجمالي إمكانات النادي في نهاية كل يوم من فترة التجنيد.

الإدخال

يحتوي السطر الأول من الإدخال على عدد صحيح $n$ ($1 \le n \le 10^5$)، يمثل عدد الأيام التي يقوم فيها النادي بتجنيد الأعضاء.

يحتوي السطر الثاني على $n$ أعداد صحيحة $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)، حيث $a_i$ هو مستوى المهارة الأولي للعضو الذي ينضم في اليوم $i$.

الإخراج

اطبع $n$ أعداد صحيحة في سطر واحد. يجب أن يكون العدد الصحيح الـ $k$ هو إجمالي إمكانات النادي في نهاية اليوم $k$.

أمثلة

الإدخال 1

8
1 2 3 1 2 3 2 3

الإخراج 1

0 0 0 0 1 3 5 9

الإدخال 2

1
1

الإخراج 2

0

ملاحظات

شرح المثال 1: في اليوم $5$، يوجد $5$ أعضاء بمستويات مهارة $[1, 2, 3, 1, 2]$. بالنسبة للعضو $1$: يوجد $3$ أعضاء انضموا لاحقاً بمهارات أعلى بشكل صارم: العضو $2$، والعضو $3$، والعضو $5$. أقصى إمكانات للعضو $1$ هي $1$، وتتحقق بأي من الاستراتيجيتين التاليتين:

• إذا بذل العضو $1$ مقدار $1$ وحدة من الجهد، تصبح مهارته $2$. سوف يلحق بالعضو $2$ والعضو $5$ أو يتجاوزهما. السعادة هي $2$ وحدة، والمكسب هو $2 - 1 = 1$ وحدة.
• إذا بذل العضو $1$ مقدار $2$ وحدة من الجهد، تصبح مهارته $3$. سوف يلحق بالأعضاء $2$ و $3$ و $5$ أو يتجاوزهم. السعادة هي $3$ وحدات، والمكسب هو $3 - 2 = 1$ وحدة.

الأعضاء الآخرون لديهم أقصى إمكانات تساوي $0$. وبالتالي، فإن إجمالي الإمكانات لليوم $5$ هو $1$.

في اليوم $8$، يوجد $8$ أعضاء بمستويات مهارة $[1, 2, 3, 1, 2, 3, 2, 3]$. الجهود المثلى هي $[2, 1, 0, 2, 1, 0, 1, 0]$ وأقصى الإمكانات المقابلة هي $[4, 2, 0, 2, 1, 0, 0, 0]$.