시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 136 61 28 36.842%

문제

n(1≤n≤1,000,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수들에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이 때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수들의 그룹이 한번에 1씩 증가한다. A[1]과 A[n]은 인접해 있다고 생각하지 않는다.

예를 들어 수들이 {1, 1, 1, 1, 3, 3, 1} 이었다고 해 보자. Add(2)를 하면 A[2]의 좌우로 인접한 같은 수들이 1씩 증가하니까 {2, 2, 2, 2, 3, 3, 1}이 된다. 여기서 Add(4)를 하면 {3, 3, 3, 3, 3, 3, 1}이 되고, 여기서 Add(1)을 하면 {4, 4, 4, 4, 4, 4, 1}이 된다.

이와 같이 Add라는 연산을 사용하여 A[1]=A[2]=A[3]=…=A[n]이 되도록 하려 한다. 이 때, 최소 회수로 Add연산을 사용하는 방법을 찾는 것이 문제이다.

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 차례로 A[1], A[2], …, A[n]이 주어진다. 모든 입력은 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 최소의 Add연산 사용 회수를 출력한다.

예제 입력

3
1
5
10

예제 출력

9

힌트

출처

  • 문제를 만든 사람: appa