Algorithm

C. Less or Equal
time limit per test
2 seconds
memory limit per test
256 megabytes
problem link- https://codeforces.com/contest/977/problem/C
input
standard input
output
standard output

You are given a sequence of integers of length n� and integer number k�. You should print any integer number x� in the range of [1;109][1;109] (i.e. 1≤x≤1091≤�≤109) such that exactly k� elements of given sequence are less than or equal to x�.

Note that the sequence can contain equal elements.

If there is no such x�, print "-1" (without quotes).

Input

The first line of the input contains integer numbers n� and k� (1≤n≤2⋅1051≤�≤2⋅105, 0≤k≤n0≤�≤�). The second line of the input contains n� integer numbers a1,a2,…,an�1,�2,…,�� (1≤ai≤1091≤��≤109) — the sequence itself.

Output

Print any integer number x� from range [1;109][1;109] such that exactly k� elements of given sequence is less or equal to x�.

If there is no such x�, print "-1" (without quotes).

Examples
input
Copy
7 4
3 7 5 1 10 3 20
output
Copy
6
input
Copy
7 2
3 7 5 1 10 3 20
output
Copy
-1
Note

In the first example 55 is also a valid answer because the elements with indices [1,3,4,6][1,3,4,6] is less than or equal to 55 and obviously less than or equal to 66.

In the second example you cannot choose any number that only 22 elements of the given sequence will be less than or equal to this number because 33 elements of the given sequence will be also less than or equal to this number.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> a;
vector<pair<int, int> > all;

int main() {
  cin >> n >> k;
  a.resize(n);
  for(int i = 0; i < n; ++i)
    cin >> a[i];

  sort(a.begin(), a.end());

  if(k == 0) {
    if(a[0] != 1)
      cout << 1 << endl;
    else
      cout << -1 << endl;
    return 0;
  }

  for(int i = 0, j, cur; i < n; ++i) {
    j = i;
    cur = a[i];
    while(i < n && a[i] == cur)
      ++i;
    --i;

    all.push_back({i - j + 1, cur});
  }

  for(int i = 0; i < all.size(); ++i) {
    k -= all[i].first;

    if(k == 0) {
      cout << all[i].second << endl;
      return 0;
    }

    if(k < 0)
      break;
  }

  cout << -1 << endl;

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
7 4
3 7 5 1 10 3 20

Output

x
–
+
cmd
6
Advertisements

Demonstration

Codeforces Solution-C. Less or Equal-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+