Problem Description

Xiao Han loves computer games, and these days he is playing a game called "Three Kingdoms".

In the game, Xiao Han and the computer each take one side, forming their own armies for battle. There are a total of $N$ generals ($N$ is an even number and not less than 4). Any two generals have a "coordination value" that represents the power of the pair when these two generals fight together. Before the game starts, all generals are free (called free generals; once a free general is selected to be part of an army, he is no longer a free general), in other words, free generals do not belong to any side.

The game begins with Xiao Han and the computer selecting generals from the free generals to form their armies. The rules are as follows: Xiao Han first selects one from the free generals to join his army, then the computer also selects one from the free generals to join the computer's army. This process continues alternately in the order of "Xiao Han -> Computer -> Xiao Han -> ..." until all generals are evenly distributed between the two sides. Then, the program automatically selects the pair of generals with the highest coordination value from each side to represent their army in a 2-on-2 duel. The pair with the higher coordination value wins, indicating that the side with the winning pair wins the battle.

It is known that the computer's principle for selecting generals is to disrupt the strongest possible combination that the opponent could form next. The specific strategy is as follows: at any time when it is the computer's turn to select, it tries to pair each general in the opponent's army with each free general to find the pair with the highest coordination value and selects that free general for its own army.

Xiao Han wants to know if there is a way for him to guarantee a win if the computer sticks to this strategy. If so, among all possible winning outcomes, what is the maximum coordination value of the pair of generals he could select for the duel?

Assume that throughout the game, both sides can always see the free generals and the opponent's army. To simplify the problem, it is guaranteed that all coordination values for different pairs of generals are unique.

Input Format

The input consists of $N$ lines.

The first line is an even number $N$, indicating the number of generals.

From the second line to the $N$-th line, the $(i+1)$-th line contains $N-i$ non-negative integers separated by spaces, representing the coordination values between the $i$-th general and the $(i+1)$-th, $(i+2)$-th, ..., $N$-th generals (where $0 \leq \text{coordination value} \leq 10^9$).

Output Format

The output consists of one or two lines.

If there exists a sequence of selections that allows Xiao Han to win the game with the given input, output $1$, and on a new line, output the maximum coordination value of the pair of generals Xiao Han could select in all winning scenarios. If there is no way for Xiao Han to win, output $0$.

Sample Input and Output

Input Sample #1

6 
5 28 16 29 27 
23 3 20 1 
8 32 26 
33 11 
12 

Output Sample #1

1
32

Input Sample #2

8 
42 24 10 29 27 12 58 
31 8 16 26 80 6 
25 3 36 11 5 
33 20 17 13 
15 77 9 
4 50 
19 

Output Sample #2

1
77

Notes/Hints

Data Range

For $40\%$ of the data, $N \leq 10$.

For $70\%$ of the data, $N \leq 18$.

For $100\%$ of the data, $4 \leq N \leq 500$. It is guaranteed that all coordination values for different pairs of generals are unique.

NOIP2010 Junior Group Problem 4

见题面 Input 部分

见题面 Output 部分