공항

시간 제한1초메모리 제한128 MB

요약

각 마을이 가져야 하는 연결 수가 주어질 때, 그 차수를 정확히 만족하는 단순 무방향 그래프를 만들 수 있는지 판정한다.

난이도: 보통10점 중 6점
유형: 그래프, 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

나라 X에는 공항을 갖춘 도시가 $n$ 개 있습니다. 각 도시 $M_i$ 는 다른 도시들과 정확히 $d_i$ 개의 양방향 항공 노선으로 연결되어야 합니다. 노선은 서로 다른 두 도시를 잇고, 양방향으로 오갈 수 있으며, 어떤 두 도시 사이에도 직항 노선은 최대 한 개만 존재할 수 있습니다(도시가 자기 자신과 연결되는 노선은 없습니다).

각 도시가 가져야 하는 연결 수 $d_1, d_2, \dots, d_n$ 이 주어질 때, 모든 도시 $M_i$ 가 정확히 $d_i$ 개의 연결을 갖도록 하는 항공망을 만들 수 있는지 판단하는 프로그램을 작성하세요. 만들 수 있으면 YES를, 만들 수 없으면 NO를 출력합니다.

입력

첫 번째 줄에 도시의 수 $n$ 이 주어집니다 ( $3 \le n \le 500$ ). 이어지는 $n$ 개의 줄에는 각 도시가 가져야 하는 연결 수 $d_i$ 가 한 줄에 하나씩 주어집니다 ( $1 \le d_i \le n-1$ ).

출력

모든 도시 $M_i$ 가 정확히 $d_i$ 개의 연결을 갖는 항공망을 만들 수 있으면 YES를, 그렇지 않으면 NO를 한 줄에 출력합니다.

예제2

예제 1
입력
```
6
2
3
2
4
1
2
```
예상 출력
```
YES
```
예제 2
입력
```
3
1
1
1
```
예상 출력
```
NO
```