No.3063 Circle Balancing
Problem Statement
You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.
You may perform the following operation any number of times, possibly $0$ times. In this operation, $A_{N+1}$ refers to $A_1$.
- Choose an integer $i\ (1 \le i \le N)$ satisfying $A_i < A_{i+1}$, and apply one of the following.
- Replace $A_i$ with $A_{i+1}$
- Replace $A_{i+1}$ with $A_i$
Find the minimum number of operations required to make all elements of the sequence $A$ equal.
It can be shown that all elements can be made equal in a finite number of operations.
Input
$N$ $A_1\ A_2\ \dots \ A_N$
- All input values are integers
- $1 \le N \le 3 \times 10^5$
- $1 \le A_i \le N$
Output
Output the minimum number of operations required. Print a newline at the end.
Sample
Sample 1
Input
3 2 3 1
Output
2
All elements can be made equal in $2$ operations by the following steps.
- Choose $i=3$ and replace $A_3$ with $A_1$. This gives $A=(2,3,2)$.
- Choose $i=1$ and replace $A_2$ with $A_1$. This gives $A=(2,2,2)$.
Sample 2
Input
5 1 5 3 3 3
Output
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tute7627
SPD_9X2