Santa Claus and Tangerines
Contest: Technocup 2017 - Elimination Round 3
Difficulty rating: 2100
Tags: binary search, data structures, greedy, two pointers

Santa Claus has n tangerines, and the i-th of them consists of exactly ai slices. Santa Claus came to a school which has k pupils. Santa decided to treat them with tangerines.

However, there can be too few tangerines to present at least one tangerine to each pupil. So Santa decided to divide tangerines into parts so that no one will be offended. In order to do this, he can divide a tangerine or any existing part into two smaller equal parts. If the number of slices in the part he wants to split is odd, then one of the resulting parts will have one slice more than the other. It's forbidden to divide a part consisting of only one slice.

Santa Claus wants to present to everyone either a whole tangerine or exactly one part of it (that also means that everyone must get a positive number of slices). One or several tangerines or their parts may stay with Santa.

Let bi be the number of slices the i-th pupil has in the end. Let Santa's joy be the minimum among all bi's.

Your task is to find the maximum possible joy Santa can have after he treats everyone with tangerines (or their parts).

Input format:
The first line contains two positive integers n and k (1 ≤ n ≤ 106, 1 ≤ k ≤ 2·109) denoting the number of tangerines and the number of pupils, respectively.

The second line consists of n positive integers a1, a2, ..., an (1 ≤ ai ≤ 107), where ai stands for the number of slices the i-th tangerine consists of.

Output format:
If there's no way to present a tangerine or a part of tangerine to everyone, print -1. Otherwise, print the maximum possible joy that Santa can have.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example Santa should divide the second tangerine into two parts with 5 and 4 slices. After that he can present the part with 5 slices to the first pupil and the whole first tangerine (with 5 slices, too) to the second pupil.

In the second example Santa should divide both tangerines, so that he'll be able to present two parts with 6 slices and two parts with 7 slices.

In the third example Santa Claus can't present 2 slices to 3 pupils in such a way that everyone will have anything.

Example input:
3 2
5 9 3

Example output:
5

Example input:
2 4
12 14

Example output:
6

Editorial:
It is obvious that if the total number of slices is less than k, then the answer is  - 1. Otherwise it's at least 1. Let's find the answer in this case.
Let's divide tangerines and parts in halves one by one in order to find the best answer. It's easy to see that it makes no sense to divide a part of size x if there is an undivided part of size y > x. So we are going to proceed dividing the largest part on each step. Let's also maintain current answer, i. e. the size of the k-th biggest current part, and a set of parts which we are going to present to the pupils. When we divide the largest part, there are two possible cases:
• If the size of any part is less then the current answer, then it's obvious that the answer will never be greater if we proceed further, so we can stop the process.
• If the sizes of both parts are greater than or equal to the current answer, then we should delete the initial part and add the resulting parts to those we present to the pupils in the current answer, and then delete the smallest part from the set making it of size k again.
We can see that in the second case the answer never decreases so we can just proceed until the first case happens.
To emulate this process in a fast way, we can keep an array from 1 to A, where A = 107 is the maximum possible number of slices in a part, where each cell contain the current number of parts of that size. Thus, we can maintain two pointers: one to the current answer and one to the current maximum size, so the whole process can be done in O(n). The overall complexity is O(n + A).