미식의 요소는 요리, 시기, 상대. 그리고⋯

하루나

평안하신가요, 하루나입니다. 벌써 새해에 있었던 일이 지나간 지 1주가 지났네요.

지난주 일을 요약하자면, 이번 새해 소동은 폐점 위기에 놓인 작은 식당 ‘참새정’을 지키기 위해, 미식연구회가 맛있는 것을 먹겠다는 집착 하나로 거대 유통 기업 ‘냐오푸드’와 맞부딪힌 이야기였습니다. 냐오푸드가 참새정을 인수해 체인점으로 만들려 하자, 우리는 가게의 운명을 걸고 요리 내기 제안을 받아들였고, 그 과정에서 구르메 헬멧단까지 끌려 들어오면서 도시 한 구석이 통째로 난장판이 되었죠. 결국 한 판 승부 끝에 참새정은 본래의 모습을 지킨 채 살아남았고, 우리는 오늘 이런 숨은 맛집들을 더 찾아 세상에 알리겠다는 좋은 목표를 하나 얻게 되었습니다.

저희 미식연구회가 엄선한 총 $N$개의 식당이 있고, $i$번째 식당은 $A_i$만큼의 맛을 가진다고 메모해 두었습니다. 저희는 $1$번 식당부터 $N$번 식당까지 순서대로 방문하는 투어를 만들 거고요. 만약 마음에 안 드는 식당이 있다면… 미리 식당을 폭파해 둘 계획입니다. $N$개의 식당 중에서 마음에 안 드는 식당을 여럿 골라 폭파하고, 그 뒤에 있던 식당들은 순서 그대로 하나씩 앞으로 당겨서 방문할 겁니다. 아, 투어 중에 음식을 먹지 않는 것은 있을 수 없는 일이니, 적어도 두 식당은 남겨두어야겠네요. 폭파하고 남은 식당들을 차례대로 방문할 때, 갈수록 더 맛있냐, 아니냐를 따질 겁니다.

참, 몇몇 식당은 선도부가 지키고 있을 수도 있습니다만… 다행히 해당 정보는 이미 저희가 입수했답니다. $S_i=\texttt{0}$이라면 $i$번 식당을 폭파해도 괜찮습니다. 하지만, $S_i=\texttt{1}$이라면 아쉽게도 폭파하기 조금 곤란하답니다. 특별한 미식 투어를 망치고 싶지는 않으니까요. 후후후.

연속해서 방문하는 두 식당을 한 쌍으로 보아 바로 다음에 가는 식당이 이전 식당보다 더 맛있으면, 그 둘의 맛의 차이만큼 저희의 기분이 좋아질 겁니다. 반대로, 다음 식당이 더 별로라면 그만큼 기분이 떨어질 거고요. 폭파하고 남은 식당을 순서대로 다 방문할 때까지 서로 이웃한 두 식당 사이의 맛의 차분을 전부 더한 값을 만족도라고 할까요? 저희가 얻을 수 있는 만족도의 최댓값이 궁금해지는군요. 그래도 최대한 다양하게 맛을 즐기고 싶기에 만족도가 최댓값인 투어 중에서 폭파하는 식당의 개수는 최소화되면 좋겠네요.

만족도를 엄밀하게 정의하자면… 우선 폭파하고 남은 식당 $M$개 중, $i$번째 식당이 $B_i$만큼의 맛을 가진다고 하죠. 그러면 만족도는

이 된답니다.

자, 선생님. 이제 만족도의 최댓값과 이때 폭파해야 하는 최소 식당 개수를 구해보죠.

모든 테스트 케이스에 대하여 $N$의 합이 $200\,000$을 초과하지 않는다.

시간 제한

1000 ms

메모리 제한

1024 MB

체커

CUSTOM