問題一覧 > 通常問題

No.1470 Mex Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 239
作問者 : 蜜蜂 / テスター : Mitarushi nok0
お気に入りにしたユーザー ProblemId : 5724 / 自分の提出
問題文最終更新日: 2021-04-09 23:36:51
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 290 (順位表) の他の問題:

Problem Statement

You are given a sequence $A_1 , A_2 , \cdots , A_N$ of $N$ integers, each at least $1$.

Also, let $\mathrm{mex} (i,j)$ be the smallest integer that is at least $1$ and is equal to neither $i$ nor $j$.

Find the sum of $\mathrm{mex} (A_i,A_j)$ over all integer pairs $(i,j)$ satisfying $1 \leq i < j \leq N$.

Input

$N$
$A_1\ \ A_2\ \ \cdots\ \ A_N$

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9(1 \leq i \leq N)$
  • All inputs are integers.

Output

Output the sum of $\mathrm{mex} (A_i,A_j)$ over all integer pairs $(i,j)$ satisfying $1 \leq i < j \leq N$, followed by a newline.

Sample

Sample 1
Input
3
2 1 1
Output
8

There are $3$ integer pairs satisfying $1 \leq i < j \leq N$: $(1,2),(1,3),(2,3)$.

  • $\mathrm{mex} (A_1,A_2)= \mathrm{mex} (2,1)=3$
  • $\mathrm{mex} (A_1,A_3)= \mathrm{mex} (2,1)=3$
  • $\mathrm{mex} (A_2,A_3)= \mathrm{mex} (1,1)=2$

Therefore, the answer is $3+3+2=8$.

Sample 2
Input
5
1 1 1 1 1
Output
20

For all integer pairs satisfying $1 \leq i < j \leq N$, $\mathrm{mex} (A_i,A_j)=2$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。