Greedy Coin Exchange

Time limit1sMemory limit64 MB

Summary

Given sorted coin denominations starting with 1, decide whether the greedy largest-coin-first method always uses the fewest coins for every amount.

Level: Medium7 of 10
Topics: Greedy, Dynamic programming, Number theory, Math
Solved: No attempts yet

Problem

The coin change problem is a standard first example of dynamic programming. It reads as follows.

To make change for $C$ won with coins of denominations $P_1, P_2, \dots, P_N$ , what is the smallest number of coins needed?

Byeongchan wants to solve it with a simple method. His method is as follows.

At each step, add one coin of the largest denomination that does not exceed the amount still missing. Repeat until the remaining amount is 0.

Byeongchan's method is not always optimal. To make 8 won from coins of 1, 4, and 6, his method uses one 6 and two 1s, three coins in total. Two 4s do it with two coins.

Byeongchan realized that his method works for some sets of denominations and fails for others. Given the denominations, write a program that decides whether his method produces the smallest number of coins for every $C$ .

Input

The first line contains the number of denominations $N$ . ( $1 \le N \le 100$ )

The second line contains the denominations $P_1, P_2, \dots, P_N$ separated by spaces. They satisfy $1 = P_1 < P_2 < \dots < P_N \le 100000$ .

Output

Print Yes if Byeongchan's method is always optimal, and No otherwise.

Examples2

Example 1
Input
```
8
1 5 10 50 100 500 1000 10000
```
Expected output
```
Yes
```
Example 2
Input
```
3
1 4 6
```
Expected output
```
No
```