1846: Монстри
Перегляд у форматі PDFЛеді замість того, щоб грати в нові ігри, такі як «5D Tetris» і «Triangle Minecraft», вона все ще грає в свою улюблену гру «Monster Killer», де, як ви вже здогадалися, вбиває монстрів.
У грі є ~N~ кімнат, пронумерованих від 1 до ~N~, і в кожній кімнаті є монстр із штучним інтелектом. Якщо сила Леді більша або дорівнює силі монстра, то вона вбиває його, переходить до наступної кімнати (якщо вона знаходиться в кімнаті ~N~, гра закінчується), і її сила збільшується на 1. Якщо її сила менша, то вона помирає (в грі, природно), і гра закінчується.
На початку сила Леді дорівнює 0. Оскільки вона має великий досвід і є відданим шанувальником гри, вона придбала «чіт-код», який дозволяє їй починати з будь-якого місця, де вона хоче.
Допоможіть Леді знайти для кожної кімнати, скільки монстрів вона зможе вбити, якщо почне з цієї кімнати.
Якщо Леді починає в кімнаті з монстром з силою більше 0, то вона негайно гине. Якщо вона починає в кімнаті 1, вона помирає в третій кімнаті, оскільки її сила дорівнює 2, а сила монстра 3. Якщо вона починає з кімнати 4 або 8, вона вбиває всіх інших монстрів і завершує гру.
Input
Перший рядок містить одне число ~N~ (~1 \le N \le 10^6~).
Наступний рядок містить числа ~a_1, a_2, … a_N~ (~0 \le a_i \le N~, для ~1 \le i \le N~), відповідні сили монстрів у кімнатах.
Output
У першому рядку виведіть ~N~ чисел, розділених пробілом, кількість монстрів, яких може вбити Леді, якщо вона почне з цієї кімнати.
Sample Input 1
8
0 1 3 0 1 1 3 0
Sample Output 1
2 0 0 5 0 0 0 1
Коментарі
добавте будьласка часу для py3
ok