Problem A. As simple as it gets ≡

Statement

Let us define that a positive integer A is simpler than a positive integer B if the decimal representation of A requires less different digits than the decimal representation of B.

For example, number 55 is simpler than 12 which in turn is simpler than 123.

Your program will be given a number N and must find the largest integer X such that X < N and X is simpler than N.

Input file format

Output file format

Constraints

1 ≤ N ≤ 2³¹ − 1

Sample tests

111

0

765437654

765377777

Explanation

Obvious solution is to decrement the number until a simpler one is obtained. This solution may require O(N × log N) operations which is too slow.

To improve that, we need to work with decimal representations N = n₁ n₂… n_K and X = x₁ x₂… x_M.

The definition of X < N gives us two cases:

1. M < K,
2. M = K and there exists some p such that x₁ = n₁, x₂ = n₂, …, x_p − 1 = n_p − 1 and x_p < n_p

In the first case the condition of maximum possible X leads us to M = K − 1 and x₁ = x₂ = …  = x_K − 1 = 9.

In the second case the same condition allows us to conclude that all digits of X after the p-th one are equal (x_p + 1 = x_p + 2 = …  = x_K). Indeed, if for some X these are different, we can replace them all with the largest of them to obtain X′ > X. The X′ will be as simple or simpler than X and still less than N.

Thus, all possible values of X can be searched by checking all combinations of p = 1… N, x_p = 0… n_p − 1, x_p + 1 = 0… 9. This solution requires O(q² × log ² N) operations, where q is the number representation base (q = 10 in this problem).