가정 채소밭이 취미인 비타로는 집의 정원에서 비바 잔디라는 식물을 키우고 있다. 현재, 비바 잔디 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에 물을 준다.

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

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

#5859 upload 14 done 9 how_to_reg 9 call_split Subtask

매우 즐거운 주말농장 timer 2s memory 1024MB

#5859
Subtask

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