| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 15 | 4 | 4 | 100.000% |
Alice and Bob own a huge company. This company was losing money consistently over the last 30 years, since its owners spent too much time playing games with mathematicians. Alice and Bob decide to make a change.
Alice and Bob start by giving unique employee IDs to each of the n employees (1 ≤ n ≤ 100, 000), where each ID I is in the range (1 ≤ I ≤ 100, 000).
Then, Alice and Bob give unique ranks to each employee. Each rank R is an integer such that 1 ≤ R ≤ 10, 000, 000. After this, they plan to reorganize the company, by making sure that the employees satisfy the following conditions:
Alice and Bob are eager to know whether their company can be reorganized successfully.
The input is a total of n + 1 lines. The first line contains n (1 ≤ n ≤ 100, 000), indicating the number of employees. On the next n lines are n distinct integers R (1 ≤ R ≤ 10, 000, 000), one integer per line, where the ith integer indicates the rank of the employee with ID i.
Output YES if the company can be reorganized successfully; output NO otherwise.
6 1 6 5 2 3 4
NO
Employee with rank 1 has employee ID 1, and thus, must be the supervisor. Employees 2 and 3 (with ranks 6 and 5) can only be supervised by employee 1 (with rank 1). However, no other employee (4, 5 or 6) can be supervised by employee 2 or employee 3, since ranks of supervisors must be smaller than the employees they supervise.
6 1 6 2 3 4 5
YES
Employee 1 (rank 1) supervises both employee 2 (rank 6) and employee 3 (rank 2).
Employee 3 (rank 2) supervises employee 4 (rank 3) and employee 5 (rank 4).
Employee 4 (rank 3) supervises employee 6 (rank 5).