필사의 문자열

면접 대비

시간 제한1초메모리 제한1024 MB

요약

소문자 문자열이 주어질 때 부분 문자열을 최대 한 번 뒤집어 사전순으로 가장 큰 문자열을 만든다.

문제

창작 슬럼프가 온 월간 향유회는 문제를 만들어내기 위한 필사적인 노력을 하고 있다.

길이 $N$ 의 영문 소문자로 이루어진 문자열이 주어진다. 당신은 이 문자열에서 부분 문자열을 하나 골라 뒤집는 수행을 최대 한 번 하려고 한다.

이때 만들 수 있는 사전순으로 가장 큰 문자열을 구해보자.

첫 번째 줄에 문자열의 길이를 나타내는 정수 $N$ 이 주어진다. ( $1 \le N \le 5\\,000$ )

두 번째 줄에 길이 $N$ 의 영문 소문자로 이루어진 문자열이 주어진다.

첫 번째 줄에 문제의 정답을 출력한다.

부분 문자열이란 어떤 문자열에서 연속된 부분으로 이루어진 문자열을 의미한다.