距離 (Distance)

Unrated

日本語

Language

Statement

\(N\) 個のボールが \(1\) 列に並べてある．左から順にボール \(1,2,\dots,N\) と呼ぶ．ボール \(i\) は色 \(C_i\) で塗られている．

各 \(i=1,2,\dots,N\) について，以下の値を求めよ．

ボール \(i\) と色が等しいすべてのボールに対する，ボール \(i\) との距離の総和．ただし，ボール \(i\) とボール \(j\) の距離は \(|i-j|\) で定義される．

入力は以下の形式で与えられる．

\(N\)
\(C_1\) \(C_2\) \(\dots\) \(C_N\)

\(N\) 行にわたり出力せよ．\(i\) 行目 (\(1 \leqq i \leqq N\)) には，ボール \(i\) と色が等しいすべてのボールに対する，ボール \(i\) との距離の総和を出力せよ．

答え以外は何も出力しないこと．(入力を促す文章なども出力しないこと．)

解答形式については，練習問題やその解答例を参考にしても良い．

Sample input 1

4
1 2 1 1

Sample output 1

ボール \(1\) が色 \(1\) で，ボール \(2\) が色 \(2\) で，ボール \(3\) が色 \(1\) で，ボール \(4\) が色 \(1\) で塗られている．

\(i = 1\) について，ボール \(1\) と色が等しいボールはボール \(1,3,4\) であり，それぞれボール \(1\) との距離は \(0,2,3\) なので \(0+2+3=5\) を出力する．
\(i = 2\) について，ボール \(2\) と色が等しいボールはボール \(2\) のみであり，ボール \(2\) との距離は \(0\) なので \(0\) を出力する．
\(i = 3\) について，ボール \(3\) と色が等しいボールはボール \(1,3,4\) であり，それぞれボール \(3\) との距離は \(2,0,1\) なので \(2+0+1=3\) を出力する．
\(i = 4\) について，ボール \(4\) と色が等しいボールはボール \(1,3,4\) であり，それぞれボール \(4\) との距離は \(3,1,0\) なので \(3+1+0=4\) を出力する．

Sample input 2

1
100

Sample output 2

ボール \(1\) が色 \(100\) で塗られている．

\(i=1\) について，ボール \(1\) と色が等しいボールはボール \(1\) のみであり，ボール \(1\) との距離は \(0\) なので \(0\) を出力する．

Sample input 3

8
1 3 9 7 3 3 7 9

Sample output 3

Sample input 4

10
1 1 1 1 1 1 1 1 1 1

Sample output 4