시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 193 44 38 24.051%

문제

Agent 욱제는 훈련소로 떠나기 전, 부모님께 큰절을 올렸다. 어릴 적, 욱제의 부모님은 욱제에게 말하곤 했다.

"욱제야, 꼭 기억하렴. Agent의 큰절은 예술적이어야 한단다."

하지만, 오늘 부모님은 욱제에게 크게 실망했다. 욱제의 큰절이 예술적이지 않다고 생각했기 때문이다. 욱제의 큰절이 예술적일 조건은 다음과 같다.

  1. 욱제의 큰절은 길이 N의 정수열 a1, …, aN으로 나타내어진다.
  2. 욱제의 큰절이 예술적이려면, 이 정수열이 일정하게 감소했다가 일정하게 증가하는 수열이어야 한다. 즉, 인덱스 2 ≤ i ≤ N - 1가 존재해, a1, …, ai는 공차 x < 0의 등차수열이고, ai, …, aN은 공차 y > 0의 등차수열이다.

당신은 욱제의 큰절을 나타내는 수열을 보고 욱제의 큰절이 예술적인지 평가해야 한다.

하지만 아뿔싸! 축구 선수 메시가 이 수열을 섞어버렸다. 순서 없이 섞인 수열을 보고 원래 욱제의 큰절이 예술적이었을 수 있을지 알아보자.

입력

첫째 줄에 수열의 길이 N이 주어진다.

둘째 줄에 욱제의 큰절을 나타내는 수열 a1, …, aN을 순서 없이 섞은 수열이 공백을 사이에 두고 주어진다.

출력

입력 수열을 재배열하여 예술적인 큰절을 나타내는 수열을 만들 수 있으면 Yes를, 아니면 No를 출력한다.

제한

  • 3 ≤ N ≤ 402,000
  • 1 ≤ ai ≤ 109

예제 입력 1

5
8 2 4 6 5

예제 출력 1

Yes

원래 수열이 6 4 2 5 8 또는 8 6 4 2 5 였으면 욱제의 큰절은 예술적이었을 것이다.

예제 입력 2

5
8 6 7 3 5

예제 출력 2

No