DMOPC '21 Contest 6 P1 - Bigger Big Integer

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 3.0s
Memory limit: 1G

Problem type

Bob is working as a data scientist, which basically means he stares at big integers all day. Bob loves big integers, and loves making them as big as possible. He is currently staring at an integer X consisting of D non-zero digits, and wants to make it bigger. However, since he doesn't want to mess up the database too much and potentially get fired, he limits himself to swapping at most one pair of adjacent digits of the integer. What is the biggest integer he can create by doing so?


2 \le D \le 10^6

All digits of X are non-zero.

Subtask 1 [2/15]

D = 2

Subtask 2 [6/15]

2 \le D \le 2 \times 10^3

Subtask 3 [7/15]

No additional constraints.

Input Specification

The first line contains an integer D.

The second line contains a D-digit integer X.

Output Specification

Output the largest integer Bob can create by swapping at most one pair of adjacent digits of X.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2



There are no comments at the moment.