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

1769. 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?


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 the positive integer that is the first number written by the monks.


Problem Author: Daniil Ayzenshteyn
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010