Canadian Computing Competition: 2011 Stage 2, Day 2, Problem 1
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 \le n \le 100\,000)~, where each ID ~I~ is in the range ~(1 \le I \le 100\,000)~.
Then, Alice and Bob give unique ranks to each employee. Each rank ~R~ is an integer such that ~1 \le R \le 10\,000\,000~. After this, they plan to reorganize the company, by making sure that the employees satisfy the following conditions:
- There is exactly one director, who has no supervisor;
- Except for the director, each employee has a supervisor, and this supervisor has a smaller employee ID and a higher rank (the value of rank is smaller); and
- Each employee can supervise at most 2 people.
Alice and Bob are eager to know whether their company can be reorganized successfully.
The input is a total of ~2~ lines. The first line contains ~n~ ~(1 \le n \le 100\,000)~, indicating the number of employees. The next line contains ~n~ distinct integers ~R~ ~(1 \le R \le 10\,000\,000)~, where the ~i~th integer indicates the rank of the employee with ID ~i~.
YES if the company can be reorganized successfully; output
Sample Input 1
6 1 6 5 2 3 4
Output for Sample Input 1
Explanation for Output for Sample Input 1
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.
Sample Input 2
6 1 6 2 3 4 5
Output for Sample Input 2
Explanation for Output for Sample Input 2
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).