Large Ping Pong Tournament

Time limit2sMemory limit512 MB

Summary

Given the total points each of 2^N players scored in a knockout ping pong tournament, decide if Dudu, who always wins ties, could have been champion.

Level: Hard9 of 10
Topics: Greedy, Sorting, Divide and conquer, Math
Solved: No attempts yet

Problem

"Don't underestimate my strength."

Dudu, 2015

This problem has the same rules as the small version and only raises the input bounds.

Dudu is spending time in Thailand and decided to enter a local ping pong tournament.

A game in this tournament is played by two players for a fixed amount of time. When the time is up, the player with more points wins, and if both players have the same number of points an arm wrestling match decides the winner. The number of points a player scores in one game is a non-negative integer.

The tournament has $2^N$ players including Dudu and proceeds in rounds. In each round the $K$ remaining players are formed into pairs and each pair plays a game. The loser of each game is eliminated and the $K/2$ winners continue to the next round. The last player remaining is the champion.

After the tournament the organizers realized that the only information they recorded is the total number of points each player scored. They did not record who played whom or who won each game, and they did not record who the champion was.

You are given the total number of points each player scored across all of his games. Dudu never loses at arm wrestling. Decide whether Dudu could have been the champion.

Input

The first line contains the integer $N$ . Each of the next $2^N$ lines contains the total number of points scored by one player, and Dudu's total is given first.

$0 \le N \le 18$ , and every total is a non-negative integer at most $10^9$ .

Output

Print YES if Dudu could have won the tournament, and NO otherwise.

Hint

In the first example one way for Dudu to win is the following. Call Dudu player 1, and number the other players 2, 3 and 4 in input order.

Round 1

Player 1 beats player 3 by 4:3.
Player 2 ties player 4 at 5:5 and wins the arm wrestling.

Players 1 and 2 continue.

Round 2

Player 1 ties player 2 at 1:1 and wins the arm wrestling.

Every player's points add up to the total given in the input. Dudu could also win in other ways, but only the possibility matters.

Examples3

Example 1
Input
```
2
5
6
3
5
```
Expected output
```
YES
```
Example 2
Input
```
1
7
7
```
Expected output
```
YES
```
Example 3
Input
```
1
4
7
```
Expected output
```
NO
```