N teams participate in the tournament. The tournament is held according to the Olympic system (teams play for elimination, the losing teams are eliminated from the tournament, the winning ones go to the next round, there are no draws). The number of teams in this problem will be a power of two: N = 2
k .
All teams are numbered from 1 to N. In the first round, teams with numbers 1 and 2, 3 and 4, 5 and 6, etc. play, in total N/2 matches are played. According to the results of these matches, the teams advance to the second round. The winners of the first and second games of the first round, the winners of the third and fourth games of the first round, etc. play in the second round. They advance to the third round. In the third round, the winners of the first and second games of the second round, the winners of the third and fourth games of the second round, etc. play together.
You are given the results of all matches. Determine the number of the team that won the tournament.
The first line of the input contains the number N – the number of teams participating in the tournament. It is a power of two and can take values from 2
0 = 1 to 2
16 = 65536. The following N − 1 lines contain the results of all matches played. The first N/2 lines of them are the results of the matches of the first round, then there are N/4 lines with the results of the second round, N/8 lines with the results of the third round, etc.
The result of each match is one of two possible numbers: 1 or 2. The number 1 means that the first team (whose number is lower) won the match, the number 2 means that the second team (whose number is higher) won the match.
The program should output a single number – number of the winning team.
| Input |
Output |
8
1
2
2
1
2
1
1 |
4 |
Answer note
Next, a tournament scheme is drawn for an example from the condition. 8 teams participated in the tournament. Match results: 1, 2, 2, 1, 2, 1, 1.
Teams 1 and 2, 3 and 4, 5 and 6, 7 and 8 played in the first round. Results of the first round matches: 1, 2, 2, 1, teams 1, 4, 6, 7 advanced to the second round.
Teams 1 and 4, 6 and 7 played in the second round. Results of the second round matches: 2, 1.
Teams 4 and 6 advanced to the third round. In the last, third round, teams 4 and 6 play, the result of the match is 1, so team 4 is the winner of the tournament.
