Twin Kiln Firing Split

EasyArrayHash tableCountingFrequencyPartitioning2 sample tests5 hidden tests

A ceramics workshop stamps every unfired tile with a numeric mold ID before it goes into a kiln. The workshop owns exactly two kilns, and every firing session loads both kilns at once with the same number of tiles. To keep the mold stamps legible after firing, a kiln must never hold two tiles that share the same stamp number in the same session — duplicate stamps warp against each other under heat. Today's batch contains an even number of tiles. Determine whether the batch can be divided into two equal-sized groups, one per kiln, such that no group contains a repeated stamp number.

Input format

Line 1: a single even integer n (2 ≤ n ≤ 100), the number of tiles in the batch.
Line 2: n space-separated integers stamp_1 ... stamp_n (1 ≤ stamp_i ≤ 100), the mold stamp number on each tile.

Output format

Print true if the batch can be split into two equal-sized groups with no repeated stamp number inside either group, otherwise print false.

Constraints

2 ≤ n ≤ 100, and n is always even.
1 ≤ stamp_i ≤ 100 for every tile.

Examples

Example 1

Input

6
1 1 2 2 3 4

Expected

true

Explanation

Stamp 1 and stamp 2 each occur twice; every other stamp occurs once. Kiln A can fire the tiles stamped 1, 2, 3 and kiln B can fire the tiles stamped 1, 2, 4 — together that uses all six tiles, and neither kiln repeats a stamp, so the split works and the answer is true.

Example 2

Input

4
1 1 1 1

Expected

false

Explanation

All four tiles share stamp 1. Each kiln can hold at most one tile stamped 1 without creating a duplicate inside that kiln, so between the two kilns at most two of these tiles have anywhere safe to go — the other two are stranded. No split avoids a repeated stamp, so the answer is false.

Ready to solve this?