두 보급소 사이의 빗길

문제

마라톤 대회의 순환 코스에는 N개의 지점이 일정한 순서로 놓여 있다. 지점에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있으며, N번 다음 지점은 1번이다. 이웃한 지점 사이에서만 이동할 수 있다. 각 지점에는 0 이상 9 이하의 정수인 내우 등급이 정해져 있고, 일부 지점에는 보급소가 설치되어 있다. 비의 세기가 정수 x일 때 내우 등급이 x 이상인 지점만 통과할 수 있다. 출발 지점과 도착 지점도 이 조건을 만족해야 한다. 운영진은 서로 다른 두 보급소를 골라 보급품을 옮기는 계획을 검토한다. 두 보급소 사이에는 시계 방향으로 가는 길과 반시계 방향으로 가는 길이 있다. 각 길은 출발 보급소에서 시작하여 해당 방향으로 이동하다가 도착 보급소에 처음 도달하면 끝난다. 따라서 한 바퀴를 더 돌거나 같은 지점을 다시 방문하지 않는다. 길의 내우 등급은 양 끝 보급소를 포함하여 그 길에 있는 모든 지점의 내우 등급 중 최솟값이다. 두 보급소의 운반 점수는 두 길의 내우 등급 중 큰 값이다. 이는 두 길 가운데 적절한 길을 골랐을 때 보급품을 옮길 수 있는 가장 강한 비의 세기와 같다. 두 길의 내우 등급이 같아도 점수는 그 값 하나로 정하며, 길을 선택하는 방법의 수는 세지 않는다. 보급소가 없는 지점도 길의 내우 등급을 결정하는 데 영향을 준다. 운영진은 가능한 모든 보급소 쌍의 운반 점수를 합하려 한다. 한 쌍에서 두 보급소의 순서는 구별하지 않는다. 서로 다른 쌍에서 같은 길이나 같은 지점을 사용하는 것은 허용되며, 각 쌍의 점수는 독립적으로 계산한다. 보급소가 두 개보다 적으면 합은 0이다. 코스의 정보가 주어질 때 이 합을 구하는 프로그램을 작성한다.

입력

첫째 줄에 지점의 수 N이 주어진다. N은 3 이상 200,000 이하의 정수다.
둘째 줄에 길이가 N인 문자열 S가 주어진다. S의 i번째 문자는 i번 지점을 나타낸다. 각 문자는 숫자 '0'부터 '9' 또는 영문 대문자 'A'부터 'J' 중 하나다. 숫자 문자는 보급소가 없는 지점이며, 내우 등급은 그 숫자의 값이다. 대문자는 보급소가 있는 지점이며, 'A', 'B', …, 'J'의 내우 등급은 각각 0, 1, …, 9다. 보급소의 수에는 별도의 하한이 없다.

출력

모든 서로 다른 보급소 쌍의 운반 점수의 합을 정수 하나로 출력한다. 보급소가 두 개보다 적으면 0을 출력한다.

4
C1E3

2

3
JJJ

27

4
0123

0

출처: Devin.KR 자체 제작