In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #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:
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).