F. Make Permutation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, ~a_2, ~\ldots, ~a_n$$$ of $$$n$$$ integers. For each element $$$a_i$$$, you can perform the following operation at most once:

  • Choose any set bit in the binary representation of $$$a_i$$$ and unset it (change it from 1 to 0).

Determine if it is possible to transform the array $$$a$$$ into a permutation of integers from 1 to $$$n$$$. A permutation of integers from 1 to $$$n$$$ is a sequence of $$$n$$$ distinct integers, each of which is between 1 and $$$n$$$ inclusive.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the elements of the array.

Output

Print "Yes" if it is possible to make the array a permutation of integers from 1 to $$$n$$$. Otherwise, print "No".

Examples
Input
3
1 3 7
Output
Yes
Input
2
1 2
Output
Yes
Input
2
3 3
Output
Yes
Input
6
3 5 2 6 5 3
Output
Yes
Note

In the first example, you can unset the first bit of $$$3 = (11)_2$$$ to get $$$2=(10)_2$$$. Then the array becomes $$$[1, 2, 7]$$$. Unset the third bit of $$$7=(111)_2$$$ to get $$$3=(011)_2$$$. We now have a permutation $$$[1, 2, 3]$$$.

In the second example, the array is already a permutation.

In the third example, you can unset the first bit of the first $$$3 = (11)_2$$$ to get $$$2=(10)_2$$$. Then the array becomes $$$[2, 3]$$$. Unset the second bit of the second $$$3=(11)_2$$$ to get $$$1=(01)_2$$$. We now have a permutation $$$[2, 1]$$$.