페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5859
서브태스크

매우 즐거운 주말농장 2초 1024MB

문제

가정 채소밭이 취미인 비타로는 집의 정원에서 비바 잔디라는 식물을 키우고 있다. 현재, 비바 잔디 i (1 ≤ i ≤ N)의 키는 Ai이다.

성장하는 비바 잔디는 특별한 품종 개량의 결과 물을 줄 때마다 키가 1 늘어난다.

모든 물을 뿌린 후 비바 잔디 i (1 ≤ i ≤ N)의 키가 B_i라면, "1 ≤ j ≤ k -1에 대해 B_j <B_{j+1}"및 "k ≤ j ≤ N - 1에 대해 B_j> B_{j+1}"을 만족하는 정수 k (1 ≤ k ≤ N)가 존재해야 한다.

다만, 비타로는 서투르기 때문에, 1회의 물을 주는데 있어서, 어느 구간 상의 비바 잔디에 일제히 물을 주는 것 밖에 할 수 없다. 즉, 물을 줄 때마다 정수 L, R (1 ≤ L ≤ R≤N)을 선택하고 비바 잔디 L, L + 1, ..., R에 물을 준다.

비타로는 물을 주는 횟수를 가능한 한 줄이고 싶다.

비바 잔디의 수와 현재 키의 정보가 주어지면 조건을 충족시키는 데 필요한 물의 횟수를 최소화하는 프로그램을 작성하십시오.


입력

입력 입력은 다음 형식으로 표준 입력에서 제공됩니다. 입력 된 모든 값은 정수입니다.

N

A_1 · · · A_N

출력

제약

• 2 ≤ N ≤ 200\,000

• 1 ≤ A_i ≤ 1\, 000\, 000 \,000 (1 ≤ i ≤ N)


출력

필요한 물 주는 횟수의 최솟값을 표준 출력에 한 줄로 출력하라.


부분문제

번호 점수 조건
#140점

N ≤ 2 000

#260점

추가 제약이 없다.


예제1

입력
5
32231
출력
3

다음과 같이 물을 3회 실시함으로써 조건을 만족시킬 수 있다.

• L = 2, R = 5로 비바 잔디 2, 3, 4, 5에 물을 준다. 비바 잔디의 키는 서쪽부터 순서대로 3, 3, 3, 4, 2가 된다.

• L = 2, R = 3으로 비바 잔디 2, 3에 물을 준다. 비바 잔디의 키는 서쪽부터 순서대로 3, 4, 4, 4, 2입니다.

• L = 3, R = 3으로 비바 잔디 3에 물을 준다. 비바 잔디의 키는 서쪽부터 순서대로 3, 4, 5, 4, 2가 된다.

2 회 이하의 물을 주어 조건을 만족시키는 것은 불가능하기 때문에 필요한 물의 횟수의 최소값은 3이다.


예제2

입력
5
97531
출력
0

이미 조건을 충족했기 때문에 필요한 물 횟수의 최소값은 0입니다.


예제3

입력
2
20212021
출력
1

한 번의 물로 조건을 만족시키기 위해서는 L = 1, R = 1로 비바 잔디 1에 물을 주거나, L = 2,

R = 2로 비바 잔디 2에 물을 주면 좋다.


예제4

입력
8
12234854912985
출력
93

출처

JOI 2021

역링크