### 2011 Canadian Computing Competition, Stage 2

## Day 2, Problem 1: Reorganization

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, consecutive positive integers starting from 1.

Then, Alice and Bob give unique ranks to each employee. Each rank is a positive integer. 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.

### Input Format

The first line contains `n`
(1 ≤ `n` ≤ 100000), indicating the number of
employees. On the next `n` lines are `n` distinct integers
`R _{i}`
(1 ≤

`R`≤ 10

_{i}^{7}), one integer per line, each indicating the rank of an employee. Employees are given in increasing order of employee ID.

### Output Format

Output `YES`

if the company can be reorganized successfully;
output `NO`

otherwise.

### Sample Input 1

6 1 6 5 2 3 4

### Sample Output 1

NO

### Explanation

Employee with rank 1 has employee ID 1, and thus, must be the director. 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 those of the employees they supervise.

### Sample Input 2

6 1 6 2 3 4 5

### Sample Output 2

YES

### Explanation

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).

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** Jun 06, 2011

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

bbi5291on Jun 08, 2011 - 5:41:07 pm UTC Error in test databbi5291on Jun 28, 2011 - 7:41:45 am UTC Re: Error in test data