{"problem":{"name":"F. World Mug (A)","description":{"content":"The 2018 WIFA World Mug is around the corner. The tournament consists of n teams. In each round of the tournament, each team plays against another team. A team that loses a match exits the tournament","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10179F"},"statements":[{"statement_type":"Markdown","content":"The 2018 WIFA World Mug is around the corner.\n\nThe tournament consists of n teams. In each round of the tournament, each team plays against another team. A team that loses a match exits the tournament, while a team that wins a match progresses to the next round. The tournament finishes when one team wins the final match.\n\nIn the first round, team 1 plays against team 2, team 3 plays against team 4, and so on. In the second round, the winner of the first match plays against the winner of the second match, and so on as shown in the picture.\n\nEach team has a certain unique strength si. Team i will win a match against team j if its strength si is greater than team j's strength sj. The number of goals scored in that match equals |si - sj|.\n\nGiven the tournament format, can you calculate the number of goals scored throughout the tournament?\n\nThe first line of input contains one integer n (2 ≤ n ≤ 218), the number of teams participating in the tournament. It is guaranteed that the number of teams is a power of two (i.e., 2, 4, 8, 16, ...).\n\nThe second line contains n *distinct* integers, the ith integer is si (1 ≤ si ≤ 109), the strength of the ith team.\n\nOn a single line, print the number of goals that will be scored in the tournament.\n\n## Input\n\nThe first line of input contains one integer n (2 ≤ n ≤ 218), the number of teams participating in the tournament. It is guaranteed that the number of teams is a power of two (i.e., 2, 4, 8, 16, ...).The second line contains n *distinct* integers, the ith integer is si (1 ≤ si ≤ 109), the strength of the ith team.\n\n## Output\n\nOn a single line, print the number of goals that will be scored in the tournament.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n = 2^k $ for some $ k \\in \\mathbb{N} $, the number of teams.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a sequence of distinct integers representing the strengths of the teams.\n\n**Tournament Structure**  \nThe tournament is a single-elimination bracket with $ n $ teams, where in each round, teams are paired consecutively:  \n- Round 1: $ (s_1, s_2), (s_3, s_4), \\dots, (s_{n-1}, s_n) $  \n- Each subsequent round pairs winners of adjacent matches from the prior round.\n\n**Match Outcome and Goal Rule**  \nIn a match between teams with strengths $ s_i $ and $ s_j $:  \n- The team with higher strength wins.  \n- The number of goals scored in the match is $ |s_i - s_j| $.\n\n**Objective**  \nCompute the total number of goals scored across all matches in the tournament:  \n$$\n\\sum_{\\text{all matches } (i,j)} |s_i - s_j|\n$$  \nwhere each match is between two teams as determined by the bracket structure.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10179F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}