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이다.

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