Yaroslav and Permutations · Interview Problem

Back to problems

Codeforces

Easy

Arrays

Math

Sorting

Yaroslav and Permutations

Determine whether an array can be rearranged so that no two adjacent elements are equal.

Acceptance 0%

Start Practice

Problem Statement

You are given an array of integers. Decide whether it is possible to reorder the elements so that every pair of neighboring elements in the resulting array contains different values.

In other words, after rearranging the array, there should be no index $i$ such that $a_i = a_{i+1}$ .

Return whether such a permutation exists.

Input Format

The first line contains an integer $n$ — the size of the array.
The second line contains $n$ integers describing the array.

Output Format

Print YES if the array can be rearranged so that no two adjacent elements are equal.
Otherwise, print NO.

Constraints

$1 \le n$
The array contains integers.
The exact original contest limits are not assumed here; solve using the standard frequency-based condition.

Examples

Sample cases returned by the problem API.

Example 1

Input

5
1 1 2 2 3

Output

YES

Explanation

One valid rearrangement is 1 2 1 3 2, where no adjacent elements are equal.

Example 2

Input

4
7 7 7 1

Output

NO

Explanation

The value 7 appears 3 times out of 4, so it cannot be placed without two 7s becoming adjacent.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress