B. Table Tennis

Codeforces

IDCF879B

Time2000ms

Memory256MB

Difficulty—

data structuresimplementation

English · Original

Chinese · Translation

Formal · Original

_n_ people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person from the line, and so on. They play until someone wins _k_ games in a row. This player becomes the winner. For each of the participants, you know the power to play table tennis, and for all players these values are different. In a game the player with greater power always wins. Determine who will be the winner. ## Input The first line contains two integers: _n_ and _k_ (2 ≤ _n_ ≤ 500, 2 ≤ _k_ ≤ 1012) — the number of people and the number of wins. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_) — powers of the player. It's guaranteed that this line contains a valid permutation, i.e. all _a__i_ are distinct. ## Output Output a single integer — **power** of the winner. [samples] ## Note Games in the second sample: 3 plays with 1. 3 wins. 1 goes to the end of the line. 3 plays with 2. 3 wins. He wins twice in a row. He becomes the winner.

#cf_span[n] 个人排成一列玩乒乓球。最初，队列中的前两名玩家进行一场比赛。然后输家走到队列末尾，赢家与队列中的下一位玩家比赛，依此类推。他们继续比赛，直到有人连续赢得 #cf_span[k] 场比赛，该玩家成为胜者。对于每位参与者，你知道他们的乒乓球实力，且所有玩家的实力值互不相同。在比赛中，实力更强的玩家总是获胜。请确定胜者的实力。第一行包含两个整数：#cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 500]，#cf_span[2 ≤ k ≤ 1012]）——人数和所需的连续胜场数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n]）——每位玩家的实力。保证该行是一个有效排列，即所有 #cf_span[ai] 互不相同。请输出一个整数——胜者的 *实力*。第二个样例中的比赛过程： #cf_span[3] 与 #cf_span[1] 比赛。#cf_span[3] 获胜。#cf_span[1] 移动到队列末尾。 #cf_span[3] 与 #cf_span[2] 比赛。#cf_span[3] 获胜。他连续赢了两次，成为胜者。 ## Input 第一行包含两个整数：#cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 500]，#cf_span[2 ≤ k ≤ 1012]）——人数和所需的连续胜场数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n]）——每位玩家的实力。保证该行是一个有效排列，即所有 #cf_span[ai] 互不相同。 ## Output 请输出一个整数——胜者的 *实力*。 [samples] ## Note 第二个样例中的比赛过程：#cf_span[3] 与 #cf_span[1] 比赛。#cf_span[3] 获胜。#cf_span[1] 移动到队列末尾。#cf_span[3] 与 #cf_span[2] 比赛。#cf_span[3] 获胜。他连续赢了两次，成为胜者。

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 2 \leq n \leq 500 $, $ 2 \leq k \leq 10^{12} $. Let $ A = (a_1, a_2, \dots, a_n) $ be a permutation of $ \{1, 2, \dots, n\} $, representing the powers of players in initial line order. **Constraints** All $ a_i $ are distinct integers in $ [1, n] $. **Objective** Simulate a tournament where: - The first two players $ a_1 $ and $ a_2 $ compete. - The loser moves to the end of the line; the winner stays and plays the next player. - The process continues until one player wins $ k $ **consecutive** games. - The player with higher power always wins. Output the **power** of the first player to achieve $ k $ consecutive wins. **Note**: If $ k > n-1 $, the player with maximum power in $ A $ will eventually win $ k $ consecutive games after defeating all others.

Samples

Input #1

2 2
1 2

Output #1

Input #2

4 2
3 1 2 4

Output #2

Input #3

6 2
6 5 3 1 2 4

Output #3

Input #4

2 10000000000
2 1

Output #4

API Response (JSON)

{
  "problem": {
    "name": "B. Table Tennis",
    "description": {
      "content": "_n_ people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person f",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF879B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_n_ people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person f...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "#cf_span[n] 个人排成一列玩乒乓球。最初，队列中的前两名玩家进行一场比赛。然后输家走到队列末尾，赢家与队列中的下一位玩家比赛，依此类推。他们继续比赛，直到有人连续赢得 #cf_span[k] 场比赛，该玩家成为胜者。\n\n对于每位参与者，你知道他们的乒乓球实力，且所有玩家的实力值互不相同。在比赛中，实力更强的玩家总是获胜。请确定胜者的实力。\n\n第一行包含两个整数：#cf_span[n] 和...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 500 $, $ 2 \\leq k \\leq 10^{12} $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $, representing the p...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments