Next Higher Number with Same Digits

Given a non-negative integer n, your task is to find the next greater number that can be formed using the exact same digits as in n. If no such number exists, output -1.

This problem can be modeled as finding the next lexicographical permutation of the digits of n. One common approach uses a modified version of the algorithm to compute the next permutation. More formally, if the digits of n are denoted by \(d_1,d_2,...,d_k\), then you must find the permutation \(d'_1,d'_2,...,d'_k\) such that:

\[ \text{next}(n) = \min\{ m > n : m \text{ is a permutation of } n \}\]

If no permutation greater than n exists, return -1.

Example:

• If \(n = 2017\), the next higher number is 2071.
• If \(n = 4321\), no higher permutation exists so the output is -1.

inputFormat

The input consists of a single line containing a non-negative integer \(n\) (\(0 \leq n \leq 10^{18}\)).

The number will be provided via standard input (stdin).

outputFormat

Output the next greater number that can be constructed by permuting the digits of \(n\). If no such number exists, output -1. The output should be printed on standard output (stdout).

## sample

12345

12354