걸그룹 여자친구에는 N명의 멤버가 있다. 편의상 각 멤버를 1번에서 N번까지의 번호로 부르자.

장태환의 i번째 멤버를 향한 덕력은 현재 A[i]이다.

장태환은 최애 멤버를 정하면서도 균형잡힌 덕질을 하기 위해 A[i]가 다음 조건을 만족하도록 덕질을 하고자 한다.

최애 멤버의 번호를 x라 할 때, 조건을 만족하는 모든 i에 대해서 A[i]<A[i+1](i+1<=x),이고, A[i]>A[i+1](i>=x)이다.
이때, 최애 멤버는 장태환이 자유롭게 선택할 수 있다.

장태환은 연속된 번호의 멤버를 골라서 덕질을 할 수 있다.

장태환이 [l,r] 범위의 멤버를 덕질할 때, A[l],A[l+1].....A[r] 모두 1씩 상승한다. 덕질을 한번 하는 데는 1일이 든다.

균형잡힌 덕질의 조건을 만족하도록 장태환이 덕질을 해야 하는 최소한의 일수를 출력하라.

균형잡힌 덕질 하기 1 timer 1s memory 1024MB

균형잡힌 덕질 하기 1 1s 1024MB