Riverside Curio

Arkady는 연속된 n일 동안 강을 관찰하기로 한다. 매일 강의 수위는 어떤 실숫값과 같다.

Arkady는 매일 강가로 가서 수로 측면의 수위 높이에 표시를 남기지만, 이전에 만든 표시와 일치하면 새 표시는 만들어지지 않는다. 물은 표시를 씻어 없애지 않는다. Arkady는 매일 수위보다 엄격히 위에 있는 표시의 수를 기록하며, i-th일째에는 이 값이 mi와 같다.

i-th일째에 수위보다 엄격히 아래에 있는 표시의 수를 di라고 정의한다. 모든 날에 대한 di의 합으로 가능한 최솟값을 구해야 한다. 첫날 전에는 수로에 표시가 없다.

첫 번째 줄에는 하나의 양의 정수 n (1 ≤ n ≤ 105) — 날짜의 수가 주어진다.

두 번째 줄에는 공백으로 구분된 n개의 정수 m1, m2, ..., mn (0 ≤ mi < i) — 매일 수위보다 엄격히 위에 있는 표시의 수가 주어진다.

모든 날에 대해 수위보다 엄격히 아래에 있는 표시의 수를 합한 값으로 가능한 최솟값을 하나의 정수로 출력한다.

첫 번째 예제에서 다음 그림은 최적의 경우를 보여 준다.

3일째에는 새 표시를 만들어야 한다는 점에 유의하라. 그렇지 않으면 4일째에 물 위에 표시가 3개 있을 수 없기 때문이다. 물속에 있는 표시의 총개수는 0 + 0 + 2 + 0 + 3 + 1 = 6이다.

두 번째 예제에서 다음 그림은 최적의 경우를 보여 준다.