You are given an array of N integers where N <= 10^5 and arr[i] >= 1 and arr[i] <= 10^6. Each time you find the sum of all the elements in the array, divide it by 2 and take the floor value. The number which is closest to this value is removed from the array, in case of tie the number with lowest id is removed. The process continues until there is single element in the array. Find the single element. The array can have duplicates.

How to solve this problem in the given time constraints. Brute force will be O(n^2)

Example :

N = 4 arr[] = 1 3 5 7

Output = 5

in first step, sum = 16, its half = 8, closest to it = 7, remove 7, now the array is 1 3 5

in second step, sum = 9, its half = 4, closest to it is 3 and 5, 3 is with lowest id, remove it, now array is 1 5

in second step, sum = 6, its half = 3, remove 1. final array is 5.

There were 3 problems, one was valid bracket sequence, other was in out dp. this was the last problem