필지 말뚝 timer 20s memory 1024MB

당신은 길이가 Kkm인 토지를 방금 샀다. 이 토지는 매우 좁아서, 이 문제에서는 동서 방향으로 뻗으며 고도가 변하는 하나의 폴리라인(polyline)으로 생각한다. 당신은 일정 간격으로 찍힌 K+1개의 측정 표식(measurement mark) M₀, M₁, ..., M_K에서의 고도(미터 단위)를 알고 있다. 이 표식들은 서쪽 끝에서부터 각각 0, 1, ..., Kkm 지점에 있다.

이 지역에서는 나무 말뚝이 서로 인접한 두 필지의 경계를 나타낸다. 나무 말뚝은 측정 표식 위치에만 놓을 수 있으며, 각 표식에는 말뚝이 최대 1개만 있을 수 있다. 현재 말뚝은 두 개가 있는데, 0km 표식에 하나, Kkm 표식에 하나가 있다. 말뚝이 있는 표식은 경계를 이루는 두 필지 모두의 일부로 취급되므로, 당신의 필지는 0km부터 Kkm까지의 모든 측정 표식을 포함한다(양 끝 포함).

어떤 필지가 매력적(desirable)이라고 간주되려면, 그 필지 안에 있는 세 개의 측정 표식이 존재하여 다음을 만족해야 한다: 그 세 표식 중 가장 서쪽과 가장 동쪽에 있는 두 표식의 고도가, 나머지 하나의 표식보다 둘 다 엄격히 높거나, 또는 둘 다 엄격히 낮아야 한다. 사람들은 풍경에 약간의 변화가 있는 것을 좋아한다! 이 세 표식은 서로 연속일 필요가 없고, 또한 그 세 표식 중 가장 서쪽/동쪽 표식이 필지의 양 끝 표식일 필요도 없다는 점에 유의하라.

예를 들어 K=5이고 M₀, M₁, ..., M_K = 5, 6, 6, 1, 2, 4라고 하자. 고도가 5, 2, 4인 표식들은 조건을 만족하고, 고도가 6, 1, 2인 표식들도 조건을 만족한다. 하지만 고도가 6, 6, 1인 표식들은 조건을 만족하지 않으며, 고도가 1, 2, 4인 표식들도 조건을 만족하지 않는다. 조건을 만족하는 임의의 세 표식이 존재하기만 하면 그 필지 전체가 매력적이다. 예를 들어 표식 값이 4 7 6 7인 필지는 앞의 세 값 때문에 매력적이다.

당신의 필지는 매력적이지만, 더 큰 가치를 뽑아낼 수 있을지도 모른다고 생각한다! 당신은 이 필지에 말뚝을 추가로 세워 여러 개의 필지로 나누고 싶다. 단, 땅을 낭비하고 싶지 않으므로, 나뉜 모든 필지는 매력적이어야 한다. 추가로 세울 수 있는 말뚝의 최대 개수는 얼마인가?