F. Find The Tree ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"Master has given Dobby a tree, Dobby is free"

Harry has opened the Chamber of Secrets and defeated the Basilisk inside using the Sword of Gryffindor. However, he won't rest until he frees his house-elf friend Dobby from his evil master Lucius. To do so, Harry will give Dobby a special gift to free him, a tree! However, he should give him a very specific tree, or else it won't count as a gift. He doesn't know what the tree looks like, but for each node in the tree, he knows the furthest node from it.

A tree, by definition, is a connected graph with $$$n$$$ nodes and $$$n-1$$$ edges. Formally, for each node $$$u\in \{1,\dots,n\}$$$, we know a node $$$v$$$ such that :

$$$$$$\mathrm{dist}(u,v) = \max_{1 \le w \le n}\mathrm{dist}(u,w)$$$$$$

where $$$\mathrm{dist}(u,v)$$$ is the minimum number of edges that have to be traversed to get from $$$u$$$ to $$$v$$$.

Harry wants to know if it is possible for such a tree to exist. Help him free Dobby.

Input

The first line in the input contains one integer $$$n:$$$ the number of vertices in the tree $$$(2 \le n \le 10^{5})$$$

The second line contains $$$n$$$ integers $$$v_{i}:$$$ the furthest node from node $$$i$$$ $$$(1 \le v_{i} \le n)$$$

Output

Print "YES" if Harry can construct the tree and "NO" otherwise.

Examples
Input
5
5 2 1 3 2
Output
NO
Input
12
7 1 9 7 11 3 1 9 7 3 3 3
Output
YES
Input
2
2 1
Output
YES
Note

In the second test case, the following tree is a possible construction: