In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
As a child Byteasar has always dreamed about reaching for the sky. Now his dream may become reality.
To achieve his goal, Byteasar has bought bricks and numbered them 1 through . All bricks have the same height but may have different width. Byteasar is planning to construct a multilevel tower. Each level should consist of a number of bricks and the total width of each level should not exceed the total width of the level located just below it (provided that the latter exists). Byteasar is fully convinced that if any brick is located at a higher level than any brick of greater identifier, the tower will fall. Byteasar's flat is too small for storing bricks, therefore Byteasar must use all the bricks that are in his possession.
Before getting to work, Byteasar asked you to find out what is the highest possible tower that he can build using the aforementioned conditions.
The first line of input contains an integer () that denotes the number of bricks. The second line holds a sequence of integers (); the number represents the width of the brick with identifier .
For the input data:
3 1 2 3
the correct result is:
Explanation of the example: The lower level of the tower contains the bricks no. and , and the upper level contains the brick no. 3.
Task author: Brian Dean (a task from USACO adapted by Adam Karczmarz).