The chief traffic policeman of the Country of Fools wants to impose a speed
limit on the motorway going from the Field of Wonders to the City of Simple Simons.
He ordered n speed limit signs. When the order arrived it turned out
that the signs had different numbers on them, which showed limits in
kilometers per hour. There were k different limits: n1
signs with the first limit, n2 signs with the second limit,
etc.; n1 + … + nk =
To make the life of drivers not so easy, the chief policeman decided to place
the signs on the motorway in such a way that a driver would have to change
speed as many times as possible. According to the traffic regulations in the
Country of Fools, a speed limitation is valid until the following speed limit
sign, and the speed shown in the sign must be observed exactly. For example, if
there is the number 60 on the sign, then a car must go until the following sign
with the speed of exactly 60 kilometers per hour.
The first line contains the number k of different types of speed limit
signs; 1 ≤ k ≤ 10000. The second line contains positive integers
n1, …, nk separated with a space.
The sum of all ni does not exceed 10000.
Output the order in which the signs must be place on the motorway, in the form
of n integers in the range from 1 to k. Assume that a driver must
change speed when the car passes by the first sign, irrespective of the
initial speed. If there are several solutions, you may output any of them.
Problem Author: Alexander Ipatov (idea by Alexander Toropov)
Problem Source: IX USU Open Personal Contest (March 1, 2008)