B - Old Maid Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋くんは、現在 N 枚のカードを持っています。 i 番目 (1\le i\le N) のカードには整数 A _ i が書かれています。

高橋くんは、以下の操作を可能な限り繰り返します。

  • 同じ整数が書かれている異なる 2 枚のカードを選び、それら 2 枚のカードを食べる。食べたカードは永久に取り除かれ、以降の操作で選ぶことはできない。

操作ができなくなったときに残っているカードに書かれている整数の合計を求めてください。

制約

  • 1\le N\le100
  • 1\le A _ i\le100\ (1\le i\le N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A _ 1 A _ 2 \cdots A _ N

出力

残ったカードに書かれている整数の合計を出力せよ。

入力例 1

8
2 7 1 8 2 8 1 8

出力例 1

15

例えば、高橋くんは以下のように操作を行います。

  1. 4 枚目のカードと 6 枚目のカードにはどちらも 8 が書かれているため、それらを選び、食べる。
  2. 1 枚目のカードと 5 枚目のカードにはどちらも 2 が書かれているため、それらを選び、食べる。
  3. 3 枚目のカードと 7 枚目のカードにはどちらも 1 が書かれているため、それらを選び、食べる。

よって、残ったカードに書かれている整数の合計は 7+8=15 です。

8 と書かれたカードは 3 枚あるので、これらのうちの 2 枚を食べると残った 1 枚は食べられないことに注意してください。

入力例 2

5
1 2 3 4 5

出力例 2

15

高橋くんが操作を一度も行えない場合もあります。

入力例 3

15
58 97 74 16 97 74 97 16 51 52 58 52 74 32 43

出力例 3

297

Score : 200 points

Problem Statement

Takahashi currently has N cards. The i-th (1\le i\le N) card has the integer A _ i written on it.

He repeats the following operation as many times as possible.

  • Choose two different cards with the same integer written on them, and eat those two cards. The eaten cards are permanently removed and cannot be chosen in subsequent operations.

Find the sum of the integers written on the cards that remain when the operation can no longer be performed.

Constraints

  • 1\le N\le100
  • 1\le A _ i\le100\ (1\le i\le N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A _ 1 A _ 2 \cdots A _ N

Output

Output the sum of the integers written on the remaining cards.

Sample Input 1

8
2 7 1 8 2 8 1 8

Sample Output 1

15

For example, Takahashi operates as follows.

  1. The fourth card and sixth card both have 8 written on them, so he chooses them and eats them.
  2. The first card and fifth card both have 2 written on them, so he chooses them and eats them.
  3. The third card and seventh card both have 1 written on them, so he chooses them and eats them.

Thus, the sum of the integers written on the remaining cards is 7+8=15.

Note that there are three cards with 8 written on them, so once two of them are eaten, the remaining one cannot be eaten.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

15

It is possible that Takahashi cannot perform the operation even once.

Sample Input 3

15
58 97 74 16 97 74 97 16 51 52 58 52 74 32 43

Sample Output 3

297