YOSEQ - Digit Subsequence

no tags 

Given a string consisting of numbers from '0' to '9', find the smallest non-negative integer that does not occur as a contiguous subsequence in the given string.

Input

Input only contains a string S (|S| <= 100000), which consists of numbers from '0' to '9'. 

Output

Output the smallest non-negative integer that does not occur as a contiguous subsequence in the given string.

Example

Input 1

0123456789

Output 1

10

Input 2

21698921085321984125

Output 2

7

Input 3

01234567891011121314151617181920

Output 3

22

hide comments
hanstan: 2018-05-16 08:25:35

just brute force will do .-.

boemogensen: 2018-05-05 03:18:27

@aditya_rev i think there is a simple adhoc solution

aditya_rev: 2018-04-30 16:32:01

Any idea for this problem? I've use binary search with some optimazion, but still got TLE._.


Added by:Ahmad Haulian Yoga Pratama
Date:2018-04-20
Time limit:0.039s-0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: SQLITE
Resource:ME