atcoder#AGC016B. [AGC016B] Colorful Hats

[AGC016B] Colorful Hats

Score : 700700 points

Problem Statement

There are NN cats. We number them from 11 through NN.

Each of the cats wears a hat. Cat ii says: "there are exactly aia_i different colors among the N1N - 1 hats worn by the cats except me."

Determine whether there exists a sequence of colors of the hats that is consistent with the remarks of the cats.

Constraints

  • 2N1052 \leq N \leq 10^5
  • 1aiN11 \leq a_i \leq N-1

Input

Input is given from Standard Input in the following format:

NN

a1a_1 a2a_2 ...... aNa_N

Output

Print Yes if there exists a sequence of colors of the hats that is consistent with the remarks of the cats; print No otherwise.

3
1 2 2
Yes

For example, if cat 11, 22 and 33 wears red, blue and blue hats, respectively, it is consistent with the remarks of the cats.

3
1 1 2
No

From the remark of cat 11, we can see that cat 22 and 33 wear hats of the same color. Also, from the remark of cat 22, we can see that cat 11 and 33 wear hats of the same color. Therefore, cat 11 and 22 wear hats of the same color, which contradicts the remark of cat 33.

5
4 3 4 3 4
No
3
2 2 2
Yes
4
2 2 2 2
Yes
5
3 3 3 3 3
No