23308번 - 셔틀버스

[그림1] 연세대학교 셔틀버스

코로나 때문에 수업은 비대면으로 운영되지만, 셔틀버스는 여전히 운영되고 있다. 물론 대부분의 경우 승객은 없다.

연세대의 셔틀버스는 순환선 방식으로, 모든 정류장에서 정차한 후 마지막 정류장에서 유턴해 동일한 길을 따라 다시 순차적으로 모든 정류장에 정차하는 것을 반복한다. 즉, 다음과 같은 노선이 있다면 백양누리 - 경영관 - 성암관 - 우정원 - 무악학사 - 우정원 - 성암관 - 경영관 - 백양누리 - ... 를 반복하는 것이다.

[그림2] 학교 셔틀버스 노선도

교양수업을 듣던 병철이는 데이터를 기반으로 주변 문제를 해결해보라는 과제를 받았으나 하도 바깥에 나간 적이 없어 주변에 무슨 문제가 발생하는지도 몰랐다. 과제를 해야 하니 큰 맘먹고 밖으로 나와 학교를 갔는데, 버스가 승객이 아닌 공기를 싣고 다니는 것을 목격했다. 이 모습을 지켜본 병철이는 번뜩이는 아이디어를 생각해냈는데, 과연 버스가 얼마나 긴 시간 동안 학생이 아닌 공기를 싣는지 조사하는 것이었다.

가장 먼저, 버스에 단말기를 설치하여 승객이 $0$명인 시점을 체크하고, 그 구간을 기록하는 프로그램을 작성하였다. 예를 들어, 백양누리를 $1$번 정류장, 무악학사를 $5$번 정류장으로 잡고 각각의 정류장을 숫자로 매겨보자. 이 노선에서 $3$ → $4$ → $5$ → $4$ → $3$ → $2$ 구간 동안 승객이 $0$명이었다면, 병철이가 작성한 코드로 인해 서버에 $[3, 4, 5, 4, 3, 2]$라는 데이터가 저장될 것이다.

데이터를 약 한 달간 모으니 엄청난 양의 정보가 모이게 되었다! 데이터가 잘 저장된 것을 보고 병철이는 머릿속에서 A+각을 그렸다. 그러나 과제와 다른 잡일에 찌든 병철이가 실수로 데이터 가공 중에 sort()를 진행해버렸다! 따라서 버스가 다닌 코스가 순서대로 찍히지 않고 정렬된 상태로 기록되어버렸다. 즉, 위의 예시 데이터가 $[2, 3, 3, 4, 4, 5]$ 이라는 데이터로 바뀌어버린 것이다.

당장 내일이 발표날이라 머릿속에선 철회각이 첨예했지만, 학기 말이라 철회도 못 한다. 코스 복원은 글렀고, 어차피 병철이에게 필요한 정보는 공기 수송이 이루어진 거리인 만큼, 그거라도 어떻게든 건지려고 한다.

병철이를 도와 F를 면하게 하자!

첫 줄에는 정류장의 수 $N (2 \leq N \leq 1\,000\,000)$, 공기수송 구간에 속하는 정류장의 수 $M (2 \leq M \leq 3\,000\,000)$이 주어진다.

두번째 줄에는 길이 $a_i (1 \leq a_i \leq 1\,000)$ 가 $N-1$개 만큼 주어지는데, $i$번째 값은 $i$번째 정류장과 $i + 1$번째 정류장 사이의 길이이다.

세번째 줄에는 공기 수송 구간 데이터가 정렬된 상태로 입력된다.

공기 수송 구간의 길이를 출력한다. 만약 가능한 길이가 두 개 이상이라면, 가장 작은 값을 출력한다.

주어진 입력 데이터로 구간을 만들 수 없다면, F 를 출력한다.