No.956 Number of Unbalanced
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 :
kroton
/ テスター :
nmnmnmnmnmnmnm
タグ : / 解いたユーザー数 32
作問者 :
kroton
/ テスター :
nmnmnmnmnmnmnm
問題文最終更新日: 2019-12-19 00:05:16
問題文
空でない整数列 $X$ について、$X$ の要素のうち過半数が同じ数である場合 $X$ は アンバランス であると呼びます。
アンバランスな例: $\{1\}$, $\{1, 2, 1\}$, $\{1, 2, 2, 2\}$
整数列 $A$ が与えられるので、$A$ にアンバランス で空でない連続する部分列が何個あるか数えてください。
ただし、列として同じでも、異なる位置から取り出された部分列は区別して数えることとします。
入力
$N$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
入力はすべて整数で与えられます。
- $ 1 \leq N \leq 10^5 $
- $ 1 \leq A_{i} \leq 10^5 $
出力
最後に改行してください。
サンプル
サンプル1
入力
6 1 2 2 3 2 3
出力
14
下記の14通りがあります。
$\{1\} ,\{1,2,2\} ,\{1,2,2,3,2\}$
$\{2\} ,\{2,2\} ,\{2,2,3\} ,\{2,2,3,2\} ,\{2,2,3,2,3\}$
$\{2\} ,\{2,3,2\}$
$\{3\} ,\{3,2,3\}$
$\{2\}$
$\{3\}$
サンプル2
入力
1 1
出力
1
サンプル3
入力
10 1 1 2 4 2 4 3 4 4 2
出力
25
サンプル4
入力
10 1 7 7 7 3 9 3 1 4 1
出力
21
サンプル5
入力
10 1 1 1 1 1 1 1 1 1 1
出力
55
サンプル6
入力
10 1 2 3 4 5 6 7 8 9 10
出力
10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。