당직 근무표

면접 대비

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

요약

N일 동안의 당직 명단을 재배열해서 같은 병사가 연속된 이틀에 당직을 서지 않게 할 수 있는지 판단합니다.

난이도: 쉬움10점 중 3점
유형: 해시맵, 그리디
정답자: 아직 제출이 없습니다

문제

중대장 만식이의 부대는 당직 근무표를 만들어 당직 근무 스케줄을 관리한다. 당직 근무표에는 총 $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
```