Module: برمجة الرسم البياني الديناميكي

Problem

أصبح ميركو الرئيس التنفيذي لشركة كبيرة. توظف الشركة N من الأشخاص ، مرقمين من 1 إلى N ، ولدى Mirko نفسه رقم 1. جميع الموظفين ، باستثناء Mirko ، لديهم رئيس. يمكن أن يكون للرئيس عدة مرؤوسين ، ولكن ليس أكثر من رئيس واحد.

عندما يتلقى Mirko تنازلًا من المستثمرين ، يسلمه إلى مرؤوسه الذي لديه أقل رقم. يقوم هذا المرؤوس أيضًا بنقلها إلى مرؤوسه الأقل رقمًا ، وما إلى ذلك ، حتى تنتقل الوظيفة إلى عامل سيئ الحظ ليس لديه مرؤوسون لإكمالها.
يحصل هذا العامل على عملة واحدة ، ويحصل رئيسه على عملتين ، ويحصل رئيس ذلك الرئيس على 3 عملات معدنية ، وهكذا. ثم يدرك الشخص الذي قام بالمهمة بالفعل مدى عدم عدالة هذا النظام الرأسمالي ويترك الوظيفة.

يتلقى Mirko التعيينات حتى يبقى موظف واحد فقط في الشركة & [مدش] ؛ ميركو نفسه. ثم أكمل هذه المهمة ، وحصل على عملة واحدة وترك الشركة.

وتساءل عن عدد العملات التي حصل عليها كل موظف سابق في المجموع. ساعده في هذا.

الإدخال:
يحتوي السطر الأول على رقم طبيعي واحد N (1 & thinsp؛ & le؛ N & le؛ & thinsp؛ 2 & middot؛ 10 ⁵ ) & mdash؛ عدد موظفي الشركة. يحتوي السطر التالي على أرقام N-1 a ₂ و ₃ و & thinsp؛ ... a _n (1 & thinsp؛ & le؛ a _i & lt؛ i)، a _i & mdash؛ رقم رئيس الموظف الأول.

الإخراج:
طباعة أرقام N ، يجب أن يشير الرقم الأول إلى عدد العملات المعدنية التي حصل عليها الموظف.

أمثلة:
نبسب ؛ <الجسم>

إدخال	الإخراج
3 1 1	5 1 1
5 1 2 2 4	13 8 1 3 1

التفسيرات:

التالي وصف للمثال الثاني.

يعطي Mirko المهمة الأولى للعامل 2 ، الذي ينقلها إلى العامل 3 ، الذي يكمل المهمة. وهكذا ، العامل 3 يتلقى عملة واحدة ، عامل 2 و [مدش] ؛ عملات معدنية ، والعامل 1 ، ميركو نفسه ، و [مدش] ؛ ثلاث عملات معدنية. بعد ذلك ، استقال الموظف 3.
يعطي Mirko المهمة الثانية إلى العامل 2 ، الذي ينقلها إلى العامل 4 ، الذي ينقل المهمة على الفور إلى العامل 5 ، الذي يكمل المهمة. بعد ذلك ، يتلقى العامل 5 عملة واحدة ، والعامل 4 و [مدش] ؛ اثنين من العملات المعدنية ، عامل 2 و [مدش] ؛ ثلاث عملات معدنية ، و Mirko & [مدش] ؛ أربع عملات معدنية. الموظف 5 يستقيل.
بعد الانتهاء من المهمة الثالثة ، يتلقى العامل 4 عملة واحدة ، والعامل 2 و [مدش] ؛ اثنين من العملات المعدنية ، و Mirko & [مدش] ؛ ثلاث عملات ، وبعد ذلك استقال الموظف 4.
بعد الانتهاء من المهمة الرابعة ، يتلقى العامل 2 عملة واحدة ، ويتلقى Mirko & [مدش] ؛ عملتين ، وبعدها يستقيل الموظف الثاني.
أخيرًا ، يتم تنفيذ المهمة الخامسة بواسطة Mirko نفسه ، حيث يتلقى عملة واحدة لهذا الغرض ، وبعد ذلك تتوقف العملية.

في المجموع ، تلقى Mirko 13 قطعة نقدية ، موظف 2 & [مدش] ؛ 8 عملات معدنية ، عامل 4 و [مدش] ؛ 3 عملات معدنية ، وعمال 3 و 5 و [مدش] ؛ عملة واحدة.