당직 근무표

면접 대비

시간 제한0.5초메모리 제한1024 MB

요약

병사 번호 수열이 주어질 때, 같은 번호가 이틀 연속 나오지 않도록 순서를 바꿀 수 있는지 판정한다.

난이도: 보통10점 중 4점
유형: 그리디, 해시맵, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

중대장 만식이의 부대는 당직 근무표를 만들어 당직 근무 스케줄을 관리한다. 당직 근무표에는 총 $N$ 일의 당직 근무 스케줄이 작성되어 있으며, 각 날짜에 한 명씩 당직을 서는 병사의 번호가 작성되어 있다. 당직 근무 이후에는 병사에게 충분한 휴식을 제공해야 하므로, 이틀 연속으로 당직 근무를 서는 것은 엄격히 금지된다.

만식이는 금지 사항을 위반하지 않기 위해, 병사들의 당직 근무 순서를 원하는 만큼 맞바꿔 당직 근무표를 개선하고자 한다. 동일한 병사가 이틀 연속으로 당직을 서지 않도록 당직 근무표를 개선할 수 있는지 확인해 주자.

입력

첫 번째 줄에 당직 근무표의 스케줄 일수 $N$ 이 주어진다. $(1\leq N\leq 100\\,000)$

두 번째 줄에 각 날짜에 당직 근무를 서는 병사의 번호를 의미하는 $N$ 개의 정수 $a\_1,\cdots,a\_N$ 이 공백으로 구분되어 주어진다. $(1\leq a\_i\leq 100\\,000)$

출력

동일한 병사가 이틀 연속으로 당직을 서지 않도록 당직 근무표를 개선할 수 있다면 YES, 아니면 NO를 출력한다.

예제3

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