W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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:
2
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).