S. 30. We would like to determine where puddles and pools are formed if the amount of precipitation is given. For simplicity, we consider only the cross-section of the given region, which is divided into horizontal line segments of fixed length with known relative altitudes. We can suppose that the distribution of precipitation is uniform.
Water flows from higher areas to the neighbouring lower ones. If a segment has two lower neighbours, then the amount of water flowing down is equally divided between those neighbours. Water on the boundary segments can only flow inward.
Write your program to determine where water finally accumulates after the rain.
The input of your program is file s30.in. The first line of this file contains 2 integers separated by a space describing the amount of precipitation in millimeters and the number N of segments (). The second line contains N integers representing the height of each segment in millimeters relative to the lowest one.
The output of your program is s30.out, containing a single line with N digits separated by spaces. The ith digit is 1, if the ith segment contains water finally, otherwise 0.
The example corresponding to the above figure is the following:
Deadline expired on 17 December 2007.