ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Old Ural Legend

Time limit: 1.0 second
Memory limit: 64 MB
According to a tale, in the sacred Indian city of Benares, beneath a temple that marked the center of the world, Brahma put three diamond needles and placed 64 gold disks on them. Priests of the temple are busy transferring the disks from needle to needle. It is believed that the world will perish as soon as the task is done.
Another legend is known in Ural. It is said that a monastery is lost in woods at the boundary of Europe and Asia, where the mythical stone flower grew. The monks who live there are doomed to write positive integers on parchment until the Last Judgement. Nobody knows when and where they started this work. There is a legend among monks that when the monastery had been built its first abbot was visited in his dream by the Archangel Gabriel, who showed a stone on the slopes of the Ural mountains where a string of digits was carved. Gabriel ordered to write all the integers starting from the smallest integer that was not a substring of that string. If this legend is true, which integer was written by the monks first?

Input

The only input line contains the nonempty string consisting of decimal digits carved on the stone. The length of the string does not exceed 105.

Output

Output the positive integer that is the first number written by the monks.

Sample

inputoutput
10123456789
11
Problem Author: Daniil Ayzenshteyn
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010
To submit the solution for this problem go to the Problem set: 1769. Old Ural Legend