Each digit at most twice

Interview

Time limit3sMemory limit256 MB

Summary

Find the largest integer L not greater than U whose decimal digits each appear at most twice.

Level: Medium5 of 10
Topics: Backtracking, Greedy, String
Solved: No attempts yet

Problem

Write a positive integer in decimal without leading zeros. The number satisfies the rule when no digit appears three or more times. For example $20152015$ satisfies the rule, and $1000$ does not because the digit $0$ appears three times.

Given a positive integer $U$ , find the largest integer $L$ with $L \le U$ that satisfies the rule. Every one-digit number satisfies the rule, so such an $L$ always exists.

Input

The first line contains an integer $U$ ( $1 \le U \le 10^{18}$ ).

Output

Print the largest integer not greater than $U$ whose decimal representation has no digit appearing three or more times.

Examples4

Example 1
Input
```
2210102960
```
Expected output
```
2210099887
```
Example 2
Input
```
1000000000000000000
```
Expected output
```
998877665544332211
```
Example 3
Input
```
1001223343
```
Expected output
```
998877665
```
Example 4
Input
```
20152015
```
Expected output
```
20152015
```