Antiarithmetic?

Time limit1sMemory limit128 MB

Summary

Given a permutation of 0 to n-1, decide whether any three positions contain values forming an arithmetic progression.

Level: Medium4 of 10
Topics: Hash map, Brute force, Math
Solved: No attempts yet

Problem

A permutation of $n$ is a bijection on the first $n$ natural numbers $0, 1, \dots, n-1$ . A permutation $p$ is called antiarithmetic if none of its subsequences of length greater than $2$ forms an arithmetic progression; that is, there are no three indices $0 \le i < j < k < n$ such that $(p_i, p_j, p_k)$ is an arithmetic progression ( $p_j - p_i = p_k - p_j$ ).

For example, the sequence $(2, 0, 1, 4, 3)$ is an antiarithmetic permutation of $5$ . The sequence $(0, 5, 4, 3, 1, 2)$ is not antiarithmetic: its first, fifth and sixth terms $(0, 1, 2)$ form an arithmetic progression, and so do its second, fourth and fifth terms $(5, 3, 1)$ .

Your task is to decide whether a given permutation of $n$ is antiarithmetic.

Input

The input contains several test cases, followed by a line containing a single $0$ . Each test case is one line: a natural number $n$ ( $3 \le n \le 10000$ ), followed by a colon (:), followed by $n$ distinct numbers separated by whitespace. These $n$ numbers are all natural numbers smaller than $n$ — i.e. a permutation of $0$ through $n-1$ .

Output

For each test case, print yes if the permutation is antiarithmetic and no otherwise, one answer per line.

Examples5

Example 1

Input

3: 0 2 1 
5: 2 0 1 3 4
6: 2 4 3 5 0 1
0

Expected output

yes
no
yes

Example 2
Input
```
3: 0 1 2
0
```
Expected output
```
no
```
Example 3
Input
```
3: 1 0 2
0
```
Expected output
```
yes
```

Example 4

Input

4: 0 2 1 3
4: 0 1 2 3
7: 0 4 2 6 1 5 3
3: 1 0 2
0

Expected output

yes
no
yes
yes

Example 5

Input

Expected output

no
yes
yes
yes
yes
no