문제

길이가 이고 각 원소가 이상 이하의 양의 정수인 배열 에 대해 아래의 연산을 수행하려고 한다.

• 배열 의 원소를 임의로 재배열한 뒤, 재배열된 배열을 한 지점에서 나누어 앞쪽 원소들로 배열 를, 뒤쪽 원소들로 배열 를 만든다. 두 배열 와 는 모두 비어 있지 않아야 한다.
• 배열 의 원소를 순서대로 이어 붙여 양의 정수 를 만들고, 배열 의 원소를 순서대로 이어 붙여 양의 정수 를 만든다.

이때 가능한 의 최댓값을 구해보자.

입력

첫 번째 줄에 배열 의 크기 이 주어진다.

두 번째 줄에 이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 가능한 의 최댓값을 출력한다.

노트

[] 길이 의 배열 을 순서대로 이어 붙인 양의 정수 의 수학적 정의는 아래와 같다.

[] 정수 와 이 아닌 정수 에 대해, 와 를 만족하는 정수 , 이 유일하게 존재하며, 이때 를 를 로 나누었을 때 나머지라 한다.

는 를 로 나누었을 때 나머지를 의미한다.