Palindrome Rearrangement

Given an array of integers, determine whether it is possible to rearrange its elements to form a palindrome. A palindrome is a sequence that reads the same forwards and backwards. In a palindrome, at most one element may appear an odd number of times. This condition can be written in LaTeX as:

$$\#\{\text{odd frequency elements}\} \le 1$$

Your task is to write a program that reads the array from standard input and outputs YES if the array can be rearranged into a palindrome and NO otherwise.

inputFormat

The first line of input contains an integer n representing the number of elements in the array. The second line contains n space-separated integers denoting the array elements.

outputFormat

Output a single line with the word YES if it is possible to rearrange the array into a palindrome, or NO otherwise.

5
3 1 2 1 3

YES