You are given an array $a$ of $n$ integers, where $n$ is odd. You can make the following operation with it:  Choose one of the elements of the array (for example $a_i$) and increase it by $1$ (that is, replace it with $a_i + 1$). 

You want to make the median of the array the largest possible using at most $k$ operations.

The median of the odd-sized array is the middle element after the array is sorted in non-decreasing order. For example, the median of the array $[1, 5, 2, 3, 5]$ is $3$.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $n$ is odd, $1 \le k \le 10^9$) — the number of elements in the array and the largest number of operations you can make.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

Print a single integer — the maximum possible median after the operations.


-----Examples-----
Input
3 2
1 3 5

Output
5
Input
5 5
1 2 1 1 1

Output
3
Input
7 7
4 1 2 4 3 4 4

Output
5


-----Note-----

In the first example, you can increase the second element twice. Than array will be $[1, 5, 5]$ and it's median is $5$.

In the second example, it is optimal to increase the second number and than increase third and fifth. This way the answer is $3$.

In the third example, you can make four operations: increase first, fourth, sixth, seventh element. This way the array will be $[5, 1, 2, 5, 3, 5, 5]$ and the median will be $5$.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left


n, k = getList()
nums = getList()
nums.sort()
half = (n // 2) + 1
nums = nums[half-1:]
sm = sum(nums)

def check(arr, k, tgt):
    for num in arr:
        sub = max(0, (tgt - num))
        if sub == 0:
            return True
        k -= sub
        if k < 0:
            return False

    return True


mn = 0
mx = 3 * (10 ** 9)
# print(nums, sm)
while(mx-mn > 1):
    md = (mx+mn) // 2
    # print(md)
    if check(nums, k, md):
        mn = md
    else:
        mx = md

if not check(nums, k, md):
    md -= 1
print(md)


import sys 
import bisect
input = lambda: sys.stdin.readline().rstrip()

n, k = list(map(int, input().split()))
arr = sorted(map(int, input().split()))
mid = arr[n//2]


s = mid
e = int(2e9)

while s <= e:
  m = (s + e ) // 2
  z = 0
  for i in range(n//2, bisect.bisect_left(arr, m)):
    if m > arr[i]:
      z += m - arr[i]
  if z > k:
    e = m - 1
  else:
    s = m + 1

print(e)

  

  



import sys
input = sys.stdin.readline

n,k=list(map(int,input().split()))
A=sorted(map(int,input().split()),reverse=True)

MIN=1
MAX=max(A)+k


while MIN!=MAX:
    AVE=(MIN+MAX+1)//2

    score=0

    for i in range(n//2+1):
        if AVE>A[i]:
            score+=AVE-A[i]

    if score>k:
        MAX=AVE-1
    else:
        MIN=AVE

print(MIN)
        
        
    


n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
id = n//2
for i in range(n//2,n-1):
    if (a[i+1]-a[i])*(i+1-id)>k:
        print(a[i]+k//(i+1-id))
        return
    else:
        k-=(a[i+1]-a[i])*(i+1-id)
print(a[-1]+k//(n-id))

[n,k] = [int(w) for w in input().split()]
a = [int(w) for w in input().split()]

a.sort()
a.append(10**57)
m = n//2
for i in range(m,n):
    dk = (i-m+1)*(a[i+1]-a[i])
    if k < dk:
        break
    k -= dk
print(a[i] + k//(i-m+1))


n, k = [int(s) for s in input().split()]
arr = sorted([int(s) for s in input().split()])
arr = arr[::-1]
arr = [pow(10, 11)] + arr[0:(n // 2 + 1)]
n = len(arr)
point = n - 1
while(k != 0):
    t = min(k, (n - point) * (arr[point - 1] - arr[point]))
    k -= t
    arr[point] += t // (n - point)
    if k != 0:
        point -= 1
print(arr[point])

# n=int(input())
n,k=(map(int,input().split()))
a=list(map(int,input().split()))
a.sort()
mid=n//2
for i in range(mid,n-1):
    if k-(a[i+1]-a[i])*(i-mid+1)>=0:
        k-=(a[i+1]-a[i])*(i-mid+1)
    else:
        print(k//(i-mid + 1) + a[i]);return
print(k//(n-mid) + a[-1])

        

def main():
    import sys
    input = sys.stdin.readline
    
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    
    arr.sort()
    arr.append(10**12)
    
    median = arr[n >> 1]
    
    i = n // 2
    while i <= n - 1 and arr[i + 1] == median:
        i += 1
    
    cnt = i + 1 - (n // 2)
    
    while i <= n:
        i += 1
        while i <= n - 1 and arr[i + 1] == arr[i]:
            i += 1
        
        diff = arr[i] - median
        if diff * cnt > k:
            ans = median + k // cnt
            break
        else:
            median += diff
            k -= cnt * diff
            cnt = i + 1 - (n // 2)
    
    print(ans)
    
    return 0

main()

n,k = list(map(int,input().split()))

A = [int(x) for x in input().split()]
A.sort()
median = A[n//2]

inf = 10**16

from collections import defaultdict as dd, deque
C = dd(int)
for x in A[n//2:]:
    C[x] += 1
C[inf] = 123

nmedian = C[median]

S = sorted(C.items())

i = 0
while i < len(S) and S[i][0] < median:
    i += 1

while True:
    who,count = S[i+1]

    afford = k//nmedian
    if who != inf:
        can =  who - median
    else:
        can = inf

    if min(afford,can) == can:
        k -= can*nmedian
        median = who
        nmedian += count
    else:
        median += afford
        break
    i += 1
print(median)




n,k=list(map(int,input().split()))
arr = list(map(int,input().split()))
arr.sort()
n //= 2
arr = arr[n:]
n+=1
med = arr[0]
flag = 1
while flag < n:
    if arr[flag]>med:
        kk = (arr[flag]-med)*flag
        if kk < k:
            k -= kk
            med = arr[flag]
        else:
            med += k//flag
            k=0
            break
    flag += 1
if flag==n:
    med += k // flag
print(med)




n, k = list(map(int, input().split()))

arr = sorted(list(map(int, input().split())))

median = arr[n // 2]

jumps = []

for i in range(n // 2 + 1, n):
    jumps.append(arr[i] - arr[i - 1])

for i in range(len(jumps)):
    weight = i + 1
    if weight * jumps[i] > k: # the median cannot go jumps[i] jumps
        this_jump = k // weight
        median += this_jump
        k -= this_jump * weight
        break
    k -= weight * jumps[i]
    median += jumps[i]

weight = n // 2 + 1
median += k // weight

print(median)


n,k=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
same=1
mid=n//2
while k>0:
	if same<=mid:
		diff=l[mid+same]-l[mid]
		temp=k
		k-=((diff)*same)
		if k>=0:
			l[mid]=l[mid+same]
		else:
			l[mid]=l[mid]+(temp//same)
	else:
		l[mid]=l[mid]+(k//(same))
		k=0
	#print (l[mid],same)
	same+=1
print (l[mid])

def mp():
    return map(int, input().split())

n, k = mp()
a = list(mp())
a.sort()

l = 1
r = 10 ** 20
while l + 1 < r:
    m = (l + r) // 2
    s = 0
    for i in range(n // 2, n):
        s += max(0, m - a[i])
    if k < s:
        r = m
    else:
        l = m

print(l)

n , k = list(map(int,input().split()))
ai = list(map(int,input().split()))
ai.sort()
num = n // 2
num2 = num
ans = ai[num]
n2 = n - 1
while num != n2 and k > 0:
    num += 1
    k -= (ai[num] - ai[num-1]) * (num - num2)
if k < 0:
    print(ai[num] + k // (num - num2))
else:
    print(ai[num] + k // (num - num2 + 1))


n, k = list(map(int, input().split()))

a = list(map(int, input().split()))

a.sort()

x = len(a)//2
rem = 1
ans = a[x]

while k > 0:
    if x+rem < len(a):
        if k >= rem*(a[x+rem]-a[x+rem-1]):
            k -= rem*(a[x+rem]-a[x+rem-1])
            ans = a[x+rem]
            rem += 1
        else:
            ans += k//rem
            k = 0
    else:
        ans += k//rem
        k = 0
print(ans)


n, k = map(int, input().split())
assert( n % 2 == 1 )
arr = sorted(map(int, input().split()))

arr = arr[n // 2:]

med = arr[0]
for i in range(1, len(arr)):
    if k == 0:
        break
    if arr[i] == med:
        continue
    else:
        diff = arr[i] - med
        kdiff = min(diff * i, k)
        med += kdiff // i
        k -= kdiff

print(med + k // len(arr))

n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
a = a[n//2:]

n = n//2+1
n_inc = 1



while m>0:
	while n_inc < n and a[n_inc-1] == a[n_inc]:
		n_inc+=1
	if n_inc == n:
		to_inc = m // n_inc
	else:
		to_inc = min(m // n_inc, a[n_inc]-a[n_inc-1])
	
	total_inc = n_inc * to_inc
	
	#print(a, n_inc, to_inc, total_inc, m)
	
	m -= total_inc
	a[n_inc-1] += to_inc
	
	
	if n_inc==n or to_inc==0:
		break
	
	
print(a[n_inc-1])
		



n, k = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]

l.sort()
l = l[n//2:]



while k != 0 :
    mini = l[0]
    compte = l.count(mini)
    if compte == len(l) :
        reste = k//len(l)
        l[0] += reste
        k = 0
        break
    deux_mini = l[compte]
    diff = deux_mini - mini
    if k >= diff*compte :
        k -= diff * compte
        for i in range(compte) :
            l[i] = deux_mini
    else :
        reste = k//compte
        l[0] += reste
        k = 0
        break

print(l[0])


import sys
input = sys.stdin.readline

n, k = list(map(int, input().split()))
l = list(map(int, input().split()))
l = sorted(l)
p = n // 2
ans = l[p]
tgt = 1
while (p < n - 1):
	diff = l[p + 1] - l[p]
	if k >= diff * tgt:
		k -= diff * tgt
		p += 1
		ans = l[p]
		tgt += 1
	else:
		print(ans + k // tgt)
		return
print(ans + k // tgt)


n, k = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
med = n // 2

def key(m):
    s = 10**10
    ind = None
    for i in range(n):
        if 0 <= m - array[i] <= s:
            s = m - array[i]
            ind = i
    if ind == None:
        return False
    if ind < med:
        return False
    else:
        for i in range(ind-1, med-1, -1):
            s += m - array[i]
        return s <= k


left = array[med]
right = 10 ** 10
while right - left != 1:
    mid = (right + left) // 2
    if key(mid):
        left = mid
    else:
        right = mid
print(left)

n, k = input().split()
n = int(n)
k = int(k)

w = input().split()
w = [int(i) for i in w]


if n == 1:
    print(w[0] + k)

else:
    w = sorted(w)
    idx = len(w)//2 + 1
    mul = 1
    gain = 0

    for i in range(idx-1, len(w)-1):
        d = w[i+1] - w[i]
        if k > d * mul:
            #remainder
            k = k - d*mul
            gain += d
        else:
            gain += k // mul
            k = k - d*mul
            break
            
        mul += 1
    # if for last elt
    if k > 0:
        gain += k // mul
    
    print(w[idx-1] + gain)
        


######################################################################
# Write your code here
import sys
import math
input = sys.stdin.readline
#import resource
#resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
#sys.setrecursionlimit(0x100000)
# Write your code here
RI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
rw = lambda : input().strip().split()
#from collections import defaultdict as df
import heapq 
#heapq.heapify(li) heappush(li,4) heappop(li)
#import random
#random.shuffle(list)
infinite = float('inf')
#######################################################################


n,k=RI()

l=RI()

l.sort()

i=n//2
median=l[i]
steps=0
count=0
while(i<n):
    temp=l[i]
    while(i<n and l[i]==temp):
        count+=1
        i+=1
    if(i<n):
        a=k//count
        if(a==0):
            break
        else:
            diff=l[i]-temp
            if(a>=diff):
                k-=(diff*count)
                median=l[i]
                continue
            else:
                k-=(a * count)
                median+=a
                break
    else:
        a=k//count
        if(a==0):
            break
        else:
            median+=a
            break
print(median)