Optimal BOT Score in a Swapping Game

You are given a 1×n grid where each cell \( (1,i) \) contains a number \( a_i \). Initially, a BOT is positioned at cell \( (1,x) \). In this game, played in rounds up to \(10^{114514}\), the following events happen in order each round:

1. The NIT’s move: The NIT selects two positions \( i,j \) (\( 1\le i,j\le n \)) and swaps \( a_i \) and \( a_j \) (if \( i=j \), nothing changes).
2. The BOT’s move: The BOT moves to an adjacent cell (or stays in place). Formally, if it is currently at \( y \), it chooses a position \( z \) such that \( |z-y|\le 1 \) and moves there; let the new position be \( y=z \).
3. Decision phase: The BOT may then choose to end the game. If it does, it receives a score equal to the number in its current cell, i.e. \( a_y \), and the game terminates immediately. Otherwise, the game continues to the next round.

To prevent the game from lasting forever, if the BOT has not ended the game by the \(10^{114514}\text{-th}\) round, it must end the game in that round.

Both players are absolutely optimal: the NIT wants the final score to be as small as possible, while the BOT wants it as large as possible. With infinitely many rounds available, the BOT can eventually reach any cell in the grid (the grid is connected via adjacent moves). However, the NIT, by swapping numbers, can sabotage promising positions – although it is allowed only one swap per round, it can always choose to lower the highest among the three cells (the current cell and its two neighbors) available to the BOT at that round.

A careful analysis shows that the final score is determined solely by the multiset of numbers on the grid. In fact, the BOT’s ultimate payoff will be:

• If n=1, the final score is \( a_1 \).
• If n>1 and the maximum number \( M=\max\{a_1,\dots,a_n\} \) appears at least twice, the final score is \( M \).
• If \( M \) is unique, then no matter what strategy the BOT employs, the NIT can always sabotage its attempt to secure \( M \) so that the best guaranteed score becomes the second largest number.

You are given \( n, x \) and the array \( a_1,a_2,\dots,a_n \). Compute the final score that the BOT can guarantee under optimal play by both sides.

Note on notation: All formulas are rendered in \( \LaTeX \) format. For example, the grid size is \( 1\times n \) and the formulas appear as \( a_i \), \( (1,x) \), etc.

inputFormat

The first line contains two integers \( n \) and \( x \) (the number of cells in the grid and the BOT's initial position, respectively).

The second line contains \( n \) integers \( a_1,a_2,\dots,a_n \) representing the numbers in the grid cells.

It is guaranteed that \( 1\leq x\leq n \) and that the input values are valid.

outputFormat

Output a single integer, the final score that the BOT will obtain under optimal play.

sample

1 1
5

5