Mad Scientist
InterviewTime limit1sMemory limit128 MB
Recover a non-decreasing sequence of measurements from its cumulative counts P(j), the number of measurements at most j, for each j from 1 to k.
- Level
Easy3 of 10
- Topics
- Array, Prefix sum, Implementation
- Solved
- No attempts yet
Problem
A mad scientist performed a series of experiments, each consisting of phases. During each phase a measurement was taken, yielding a positive integer of magnitude at most . Every experiment was designed so that its measurements were monotonically non-decreasing: each measurement is at least as large as all measurements that precede it. For example, one experiment with and produced the following measurements:
1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 6
Because was always larger than , the measurement sequence typically contained many repeated values. Being mad, the scientist recorded the data in an unusual way. Instead of storing all measurements, the scientist stored a sequence of values where, for , is the number of phases whose measurement is at most . For the experiment above, the measurements were recorded as the -sequence:
2, 7, 7, 8, 12, 13
because two measurements are , seven are , seven are , and so on.
The scientist eventually went insane, leaving behind a notebook full of these -sequences. Write a program that recovers the original measurements from each -sequence.
Input
The input contains several -sequences, one per line. Each line begins with the integer , the length of the -sequence, followed by the values of the sequence. The input ends with a line containing a single . Every original experiment satisfied .
Output
For each -sequence, print one line containing the recovered measurements of the original experiment, separated by single spaces.