問題一覧 > 通常問題

No.3063 Circle Balancing

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : 👑 tute7627 / テスター : 👑 rin204 SPD_9X2
お気に入りにしたユーザー ProblemId : 11168 / 自分の提出
問題文最終更新日: 2025-03-12 02:47:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 460 (順位表) の他の問題:

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.

  1. Choose $i=3$ and replace $A_3$ with $A_1$. This gives $A=(2,3,2)$.
  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もしくは右上の雲マークをクリックしてアカウントを作成してください。