시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 256 MB (%)
문제
앨리스와 밥은 거대회사의 주인이다. 이 회사는 주인들이 너무 많은 시간을 수학 게임을 하는데 보냈기 때문에 30년동안 지속적으로 돈을 잃어왔다. 앨리스와 밥은 변화를 주기로 했다. 앨리스와 밥은 각각 n명의 직원들에게 유일한 고유 ID를 주었다. (1<=n<=100,000) 각각 ID I는 다음의 범위안에 있다. (1<=I<=100,000) 그리고, 앨리스와 밥은 각 직원들에게 유일한 순위를 주었다. 각 순위 R은 1<=R<=10,000,000를 만족하는 정수이다. 그 후에, 그들은 회사를 개편하는 계획을 만들었는데, 그것은 아래의 조건들을 직원들이 만족하도록 하는것이다: 1. 상사가 없는 정확히 한명의 임원이 존재한다. 2. 임원을 제외하고, 각 직원들은 상사를 갖는다. 상사는 이 직원보다 직원 ID가 더 작아야하고, 순위가 더 높아야한다. (순위의 수치가 더 낮아야한다.) 3. 각 직원들은 최대 두명의 상사가 될 수 있다. 앨리스와 밥은 이 재개편이 성공적으로 할 수 있는지 알고싶다.
입력
입력은 총 n+1개의 줄로 이루어진다. 첫줄에 직원수 n(1<=n<=100,000)이 주어진다. 그 뒤 n개의 줄에 n개의 다른 정수 R(1<=R<=10,000,000)이 한줄에 하나씩 주어진다. i번째 줄에 있는 순위를 갖는 직원은 ID가 i이다.
출력
만약 재개편이 성공적으로 할 수 있으면 YES, 아니면 NO를 출력한다.
힌트
입력예제1 ``` 6 1 6 5 2 3 4 ``` 출력예제1 ``` NO ``` 예제1설명 직원1이 순위가 1이므로, 임원이 되어야한다. 직원 2와 3은(순위 6과 5) 직원 1 (순위 1)을 상사로 가져야한다. 하지만, 직원 4,5,6은 직원 2,3을 상사로 둘 수 없다. 직원 4,5,6의 순위가 직원 2,3의 순위보다 더 좋기 때문이다. 고로 불가능하다. 입력예제2 ``` 6 1 6 2 3 4 5 ``` 출력예제2 ``` YES ``` 예제2설명 직원 1(순위 1)은 직원 2(순위 6)와 직원 3(순위 2)의 상사로 한다. 직원 3(순위 2)은 직원 4(순위 3)과 직원 5(순위 4)의 상사로 한다. 직원 4(순위 3)은 직원 6(순위 5)의 상사로 한다.