该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Background

Muxue the youth is studying an interesting mathematical problem: given a cyclic sequence, each operation can increase a number by 1. He wants to know the minimum number of operations required to turn the sequence into a cyclic arithmetic progression.

Problem Description

Muxue has a cyclic sequence of length n (the head and tail are connected). In each operation, he can choose a number in the sequence and increase it by 1.

Muxue wants to know the minimum number of operations required to make all numbers in the sequence equal.

Note: Since only increasing is allowed and decreasing is not, eventually all numbers will become the maximum value in the original sequence.

Input Format

First line: an integer n (3 ≤ n ≤ 10^5)
Second line: n integers a₁, a₂, ..., aₙ (0 ≤ aᵢ ≤ 10^9)

Output Format

An integer, representing the minimum number of operations.

Sample Input and Output #1

Input #1

4
1 2 3 4

Output #1

6

Explanation/Notes

Explanation for Sample 1: The maximum value is 4, requiring operations (4-1)+(4-2)+(4-3)+(4-4) = 3+2+1+0 = 6 times.

This problem uses Subtask bundled testing