31231번 - 마카롱카마

문제

요정의 나라에서 마카롱 만들기 대회가 열렸다! 마카롱은 두 개의 구워진 코크 사이에 원하는 필링을 넣어서 만드는 디저트이다. 룰루는 대회에 참가하기 위해서 우선 마카롱에 사용될 코크들을 만들었다. 룰루는 빨간색 코크 $N$개를 만들어서 바닥에 두었다. $i$번째 빨간색 코크의 크기는 $a_{i}$이다. 또한 $N$개의 파란색 코크도 만들었으며, $i$번째 파란색 코크의 크기는 $i$번째 빨간색 코크의 크기와 같다.

마카롱 만들기 대회에는 특별한 룰이 있다. 각 마카롱의 크기는 1ドル$ 이상 9ドル$ 이하의 정수여야 하고, 마카롱의 총개수는 $N$개여야 한다. 참가자가 받게 되는 점수는 1ドル$번째부터 $N$번째까지의 마카롱의 크기를 순서대로 적었을 때 만들어지는 수이다. 예를 들어서 $N = 4$인 경우 $i$번째 마카롱의 크기를 $m_{i}$라고 하면, $(m_{1}, m_{2}, m_{3}, m_{4}) = (1, 4, 2, 3)$일 때 참가자가 얻는 점수는 1423ドル$점이다. 이때, 얻은 점수가 가장 큰 참가자가 대회에서 우승한다.

룰루는 바닥에 놓아둔 $i$번째 빨간색 코크에 각각 $i$번째 파란색 코크를 올려서 마카롱 만들기를 마무리 지으려고 했으나, 대회에서 이기기 위해서 꼼수를 부리기로 했다. 바닥에 놓아둔 빨간색 코크의 순서는 유지하되, 파란색 코크는 원하는 위치의 빨간색 코크 위에 마음대로 올리기로 하였다. 이렇게 $N$개의 마카롱을 만든 후, 빨간색 코크와 파란색 코크 중 크기가 더 큰 코크를 위로 가게 두면 요정들은 더 큰 코크의 크기가 해당 마카롱의 크기라고 착각하게 될 것이다.

그러나 이를 옆에서 요정 픽시가 지켜보고 있었고, 꼼수를 허용하는 대신 룰루가 얻은 점수가 팰린드롬수가 되도록 마카롱을 만들어 달라고 요청했다. 팰린드롬수는 숫자들을 앞에서부터 읽은 것과 뒤에서부터 읽은 것이 같은 수이다. 예를 들어 12321ドル$은 팰린드롬수지만, 3141ドル$은 팰린드롬수가 아니다. 픽시의 요청을 받아들이면서 룰루가 얻을 수 있는 최대 점수를 구해보자.

입력

첫째 줄에 룰루가 만들어둔 빨간색 코크의 개수 $N$이 주어진다. $(1\leq N\leq 400)$

둘째 줄에 룰루가 만들어둔 빨간색 코크들의 크기를 나타내는 길이 $N$의 문자열이 주어진다. $i$번째 문자는 $i$번째 빨간색 코크의 크기를 나타내며, 1ドル$ 이상 9ドル$ 이하이다.

출력

첫째 줄에 룰루가 얻을 수 있는 최대 점수를 출력한다.

제한

힌트