Праздничные дни
Жителі Флатландії дуже полюбляють свята. Вони вважають, що довільна більш-менш важлива пам'ятна дата заслуговує того, щоб її відмітити. Тому у Флатландії дуже багато державних свят. Настільки багато, що там немає навіть звичайних вихідних (як субота і неділя у Росії) — жителям цілком вистачає державних свят.
У кожного свята є день, коли воно повинно відмічатись. При цьому день багатьох свят визначається за дуже складними правилами; наприклад, День захисту Флатландських вовків відмічається в останій повний місяць року, Міжнародний День СУНЦів — в 42-й день літніх канікул, а День Флатландського метеоролога — на наступний день після першого дощового літнього четверга. (Правда, флатландські метеорологи настільки суворі, що можуть передбачити, на який день припаде їх професійне свято, за рік до нього.)
Звичайно, що при такій складній і заплутаній системі свят часто трапляється так, що декілька свят припадають на один і той же день. Але флатландці — дуже систематичні люди, і вони не можуть відмічати декілька свят у один і той же день, тому у таких випадках свята потрібно переносити.
Природньо, що просто так переносити свята не можна. Перенесення свята допускається лише при умові, що всі дні між правильною датою свята і тим днем, на який це свято переноситься, також будуть святковими. Строго кажучи, свято з дня i можна відмічати у день j при одній з двох наступних умов:
або i=j,
або i≠j, але при цьому у день i, а також у всі дні між i та j невключно відмічаються якісь інші свята (зверніть увагу, що може бути як i < j, так і i > j).
Таким чином, весь рік буде складатись з блоків робочих та вихідних днів, що чергуються, і перенесення свята допустимо лише при умові, що воно потрапляє у той же блок.
Флатландці — послідовні люди, і дотримуються принципу "працювати — так працювати, відпочивати — так відпочивати". Тому вони не люблять частих змін вихідних і робочих днів. Тому свята повинні бути перенесено так, щоб середня довжина блоків вихідних днів була найбільшою.
Сьогодні у Флатландії, як і у всьому світі, настає Новий рік. Через декілька годин президент Флатландії виступить зі зверненням перед громадянами. За традицією, він повинен озвучити календар вихідних і робочих днів на наступний рік. Цей розклад повинен був підготувати Міністр Флатландії по Святам, але, на жаль, учора відмічався День Міністрів Флатландії, і тому Міністр не встиг підготувати календар — і не вспіє, так як комп'ютером користуватись він не вміє, а вручну складання календаря займає багато часу.
Тому підготувати календар доручено вам. Напишіть програму, яка, знаючи, на який день скільки свят припадає, перенесе їх у відповідності з правилами. Врахуйте, що не можна свята відмічати раніше першого дня року, і не можна їх відмічати пізніше останнього дня.
Вхідні дані
У першому рядку вхідного файлу знаходиться одне число n — кількість днів у Флатландському році (1 ≤ n ≤ 4000). У другому рядку знаходяться n невід'ємних цілих чисел, i-те з яких вказує, скільки свят припадає на i-ий день року.
Гарантується, що сума всіх чисел у другому рядку вхідного файлу не перевищує n.
Вихідні дані
Виведіть у вихідний файл n символів: для кожного дня року виведіть, повинен він бути вихідним чи робочим. Виводьте символ 'X' (латинська велика літера X) для робочого дня і символ '*' (зірочка) для вихідного.