Holidays
Residents of Flatland are passionate about holidays. They believe that any significant date deserves a celebration, resulting in a multitude of public holidays. In fact, there are so many holidays that traditional weekends (like Saturday and Sunday in Russia) are unnecessary, as the residents enjoy ample public holidays.
Each holiday has a designated day for celebration, but many are determined by intricate rules. For instance, Flatland Wolf Protection Day is observed on the last full moon of the year, International Day of SUNCs on the 42nd day of summer vacation, and Flatland Meteorologist Day on the day following the first rainy summer Thursday. Remarkably, Flatland meteorologists can predict their holiday date a year in advance.
Given this complex holiday system, it's common for multiple holidays to coincide on the same day. However, Flatlanders are methodical and cannot celebrate multiple holidays simultaneously, necessitating the rescheduling of some holidays.
Rescheduling is not arbitrary. A holiday can only be moved if all the days between its original date and the new date are also holidays. Specifically, a holiday on day i can be celebrated on day j if:
i = j, or
i ≠ j, but every day between i and j exclusively is also a holiday (this applies whether i < j or i > j).
Thus, the year is divided into alternating blocks of working and holiday days, and rescheduling is only allowed within the same block.
Flatlanders value consistency, following the principle "work — then work, rest — then rest." They prefer fewer transitions between holidays and working days, aiming to maximize the average length of holiday blocks.
As the New Year approaches, the President of Flatland is set to announce the holiday and work schedule for the coming year. Traditionally, this schedule is prepared by the Flatland Minister of Holidays. However, due to Flatland Ministers' Day yesterday, the Minister was unable to complete the task and lacks the skills to compile it manually in time.
Thus, you are tasked with preparing the calendar. Write a program that, given the number of holidays on each day, will reschedule them according to the rules. Note that holidays cannot be scheduled before the first day of the year or after the last day.
Input
The first line of the input contains a single number n — the number of days in the Flatland year (1 ≤ n ≤ 4000). The second line contains n non-negative integers, where the i-th number indicates how many holidays fall on the i-th day of the year.
It is guaranteed that the sum of all numbers in the second line does not exceed n.
Output
Output n characters: for each day of the year, indicate whether it should be a holiday or a working day. Use the character 'X' (uppercase Latin letter X) for a working day and the character '*' (asterisk) for a holiday.