Chef and Linear Chess Problem Code: LINCHESS

Read problem statements in Hindi, Bengali, Mandarin Chinese, Russian, and Vietnamese as well.

Chef wants to play a game of linear chess on a one-dimensional board ― an infinite row of squares numbered by positive integers. In this game, he has a pawn, which is initially at a square . There are also  other people (numbered  through ); Chef can choose one of them to play against. For each valid , the -th player would play in the following way:
  • Take a pawn and place it on a square .
  • Repeat the following move any number of times: move the pawn from its current square  squares forward, i.e. from a square , this player's pawn is moved to the square .
  • If this player moves their pawn to the square with Chef's pawn, then Chef's pawn is captured and he loses the game.
Unfortunately, Chef cannot move his pawn during the game, making him an easy target for other players. Given the starting positions of all  players, find a player who can capture Chef's pawn in the smallest number of moves or determine that no player can capture his pawn.


  • The first line of the input contains a single integer  denoting the number of test cases. The description of  test cases follows.
  • The first line of each test case contains two space-separated integers  and .
  • The second line contains  space-separated integers .


For each test case, print a single line containing one integer ― the starting square of one player that can beat Chef in the smallest number of turns, or  if no player can beat him.
If there are multiple solutions, you may find any one.


  •  for each valid 
  •  are pairwise distinct


Subtask #1 (100 points): original constraints

Example Input

4 6
4 3 2 8
4 7
4 3 2 8

Example Output



Example case 1: The player who starts at the position  can move to square and then to square . The player who starts at the position  can move to square . The player at position  can capture Chef's pawn in  turns, whereas the player at position  can capture Chef's pawn in  turn. Therefore, the answer is .
Example case 2: No player can capture Chef's pawn.


Popular posts from this blog

How to pass parameters in webhook?

Access and modify all the resources of our Wiki.js using WikiJS API

Fahrenheit to Celsius