Increasing Sequence

You are given a string consisting only of decimal digits. Split it into one or more contiguous substrings to form a sequence. Each substring is interpreted as an integer, and leading zeroes are allowed.

After the split, the sequence must be strictly increasing: every number must be larger than the previous one. Among all valid increasing sequences, minimize the value of the last number and output that value.

The first line contains the digit string. Its length is between 1 and 80, inclusive.

Print the minimum possible value of the last number in a valid increasing sequence. If the last substring has leading zeroes, omit them when printing; if its value is 0, print 0.