시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 87 23 19 28.788%

문제

0 이상 1 미만인 두 수 $x$, $y$에 대하여, 그 둘의 거리 $d(x, y)$를 다음과 같이 정의하자.

$\displaystyle d(x, y) = \min \left\{ | x-y | , 1 - | x-y | \right\}$

$0 \le A_1 \le A_2 \le \cdots \le A_N < 1$을 만족하는 길이 $N$의 수열 $A$에 대하여, 이의 분포 정도 $f(A)$를 다음과 같이 정의하자.

$\displaystyle f(A) = \sum_{1 \le i < j \le N} d(A_i, A_j)$

길이 $N$인 수열 $A$가 주어질 때, 길이가 $N$이면서 $A$보다 분포 정도가 큰 수열이 존재하는지 판별하는 프로그램을 작성하시오.

즉, $f(A) < f(B)$를 만족하는 길이 $N$의 수열 $B$가 존재하는지 여부를 판별하는 프로그램을 작성하시오.

입력

첫번째 줄에 수열의 길이를 의미하는 자연수 $N$이 주어진다.

두번째 줄에 $N$개의 유리수 $A_1, A_2, \cdots, A_N$이 사이에 공백을 두고 주어진다.

하나의 유리수는 "$p$/$q$" 형태로 주어지며, 이는 그 수가 $\displaystyle \frac{p}{q}$임을 의미한다. 여기서 $p$와 $q$는 정수며, $0 \le p < q \le 10^9$임이 보장된다.

출력

만약 길이가 $N$이면서 $A$보다 분포 정도가 큰 수열이 존재한다면, 첫번째 줄에 "YES"를 출력한다.

만일 그렇지 않다면, 첫번째 줄에 "NO"를 출력한다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

  • $2 \le N \le 10^6$
  • $0 \le A_i < 1$ $(1 \le i \le N)$
  • $A_i \le A_{i+1}$ $(1 \le i < N)$

예제 입력 1

2
0/1 1/2

예제 출력 1

NO

예제 입력 2

2
0/1 2/3

예제 출력 2

YES

예제 입력 3

3
0/1 1/6 1/3

예제 출력 3

YES