원형 수열 줄이기

$N\le200\,000$이므로 삭제 순서를 모두 시도할 수는 없다. 최종 두 원소를 남길 수 있는 조건을 원래 인접 원소들의 관계로 바꾸는 것이 핵심이다.

두 끝점 사이를 모두 지울 수 있는 조건

먼저 선형으로 나열된 경로의 양 끝 $a<b$만 남기려 한다고 하자. 내부 원소를 모두 지울 수 있을 필요충분조건은 원래 경로에 인접한 오름차순 쌍 $u,v$가 있어
\[ u\le a<b\le v \]
를 만족하는 것이다.

필요성을 보자. 극값 $t$를 지워 새 오름차순 쌍 $p<q$가 생겼다면 $t>q$ 또는 $t<p$이다. 전자에서는 삭제 직전의 오름차순 쌍 $p,t$가, 후자에서는 $t,q$가 값의 구간 $[p,q]$를 포함한다. 마지막 쌍 $a,b$에서 이 관계를 역추적하면 $[a,b]$를 포함하는 원래의 인접 오름차순 쌍을 찾는다.

충분성을 위해 조건을 만족하는 $u,v$를 고정하자. $a$부터 $u$까지와 $v$부터 $b$까지에서 내부 극값을 더 없앨 수 없을 때까지 지운다. 서로 다른 값으로 이루어진 경로에 내부 극값이 없으면 단조하며, 두 부분의 끝값에 의해 모두 감소하는 경로가 남는다.

이제 왼쪽 부분의 오른쪽 끝부터 지우면 오른쪽에 큰 값 $v$가 있으므로 매번 국소 최솟값을 지우게 된다. $a$만 남긴 뒤 오른쪽 부분의 왼쪽 끝부터 지우면 매번 국소 최댓값을 지우게 된다. 따라서 $a,b$만 남길 수 있다. $u=a$나 $v=b$이면 해당 쪽에서 지울 부분이 없다.

오름차순 간선과 내림차순 간선의 겹침

원형 수열에서 $a<b$를 남기려면 양쪽 경로를 모두 지워야 한다. 위 성질에 따라 한쪽에는 $[a,b]$를 포함하는 시계 방향 오름차순 쌍이, 다른 쪽에는 같은 구간을 포함하는 시계 방향 내림차순 쌍이 필요하다.

반대로 오름차순 쌍과 내림차순 쌍의 값 구간이 겹친다고 하자. 낮은 끝점 중 큰 값을 $a$, 높은 끝점 중 작은 값을 $b$로 두고 $a<b$라고 하자. $a,b$는 실제 원소이며 두 인접 쌍이 모두 $[a,b]$를 포함한다.

$a$는 두 쌍의 낮은 끝점 중 하나이고 $b$는 높은 끝점 중 하나이다. 따라서 $a$에서 $b$로 가는 시계 방향 경로에는 오름차순 쌍이 놓이고, 반대 경로에는 내림차순 쌍이 놓인다. 같은 쌍의 두 끝점이 선택된 경우에도 그 쌍은 한쪽 경로이고 다른 쌍은 반대 경로에 남는다. 각 경로에 앞의 성질을 적용하면 실제로 $a,b$만 남길 수 있다.

결국 오름차순 인접 쌍과 내림차순 인접 쌍의 값 구간을 하나씩 골라, 겹치는 길이를 최대화하면 된다.

작은 끝점부터 처리하기

원소를 값순으로 정렬해 작은 값 $x$부터 처리한다. 원래 위치의 다음 원소가 더 크면 그 값을 오름차순 구간의 높은 끝점 후보로, 이전 원소가 더 크면 그 값을 내림차순 구간의 높은 끝점 후보로 넣는다.

지금까지 얻은 두 방향의 높은 끝점 최댓값을 각각 $R,L$이라 하면 현재 확인할 후보는
\[ \min(L,R)-x \]
이다. 두 방향의 후보가 아직 없거나 값이 양수가 아니면 무시한다.

가능한 최종 쌍 $a<b$에 대해서는 $x=a$를 처리할 때 두 방향 모두 높은 끝점이 $b$ 이상인 구간이 등록되어 있다. 따라서 그 차 이상인 후보를 반드시 확인한다.

한편 어떤 양수 후보도 실제 두 구간의 겹침 길이보다 크지 않다. 두 낮은 끝점의 최댓값은 $x$ 이하이고, 높은 끝점의 최솟값은 $\min(L,R)$이기 때문이다. 그 겹침은 앞에서 실제로 남길 수 있음을 보였으므로 후보가 최적값을 넘을 수도 없다. 따라서 후보의 최댓값이 정확히 답이다.

원래 양옆 위치만 확인하며 첫 원소와 마지막 원소도 이웃으로 처리한다. 시간복잡도는 $O(N\log N)$, 공간복잡도는 $O(N)$이다.