Ravi and Shanu play a game.
Initially they write N random numbers on a sheet of paper. Suppose the integers written are a1, a2, a3 …..,an. Now they start playing a game. In each turn a player selects a number and erases it from the sheet. They play alternatively. Ravi makes the first move. This continues until there is only one number left on the sheet.
Ravi wants to minimize the last number that would be the left on sheet. While Shanu wants to maximize it.
You want to know the last number that would be left on the sheet if both Ravi and Shanu play optimally.
You are given the numbers which they initially wrote on the board.
Input Format:
The first line contains an integer N, denoting the number of elements in Numbers. Each line i of the N subsequent lines (where 0 <= i < N) contains an integer describing Numbers i.
Constraints:
1 <= N <= 5000 1 <= Numbers[i] <= 10 ^ 5
Sample Input 1:
1 1
Sample Output:
1
Explanation:
There is only one number which would be left on the sheet of paper.
Sample Input 2:
3 2 2 2
Sample Output:
2
Explanation:
It is obvious the answer will be 2 as all numbers written by them are 2.
Sample Input 3:
3 2 1 3
Sample Output:
2
Explanation:
Ravi will erase 3 while Shanu will erase 1. Hence 2 will be left on the sheet.
Let's see the Implementation:
N = int(input()) temp = N arr = [] # taking input of N numbers while temp != 0 : i = int(input()) arr.append(i) temp -= 1 temp = [] # sort array in ascending order arr.sort() for i in range(N // 2) : temp.append(arr[-(i + 1)]) temp.append(arr[i]) if N == 1: print(arr[0]) elif N // 2 == 0 : print(temp[-1]) else : print(arr[N // 2])