sorting_algos

#include<bits/stdc++.h>
using namespace std;
// void merge(int *a, int Start, int Mid, int End)
// {
//     int temp[End - Start + 1];
//     int i = Start;
//     int j = Mid + 1;
//     int k = 0;
//     while (i <= Mid && j <= End)
//     {
//         //observation->operations
//         if (a[i] < a[j])
//         {
//             temp[k] = a[i];
//             i++;
//         }
//         else
//         {
//             temp[k] = a[j];
//             j++;
//         }
//         k++;
//     }
//     //for the left out elements
//     while (i <= Mid)
//     {
//         temp[k] = a[i];
//         k++;
//         i++;
//     }
//     while (j <= End)
//     {
//         temp[k] = a[j];
//         k++;
//         j++;
//     }
//     for ( i = Start; i <= End; i++)
//     {
//         a[i] = temp[i - Start];
//     }
// }
// void mergesort(int *a, int start, int end)
// {
//     if (start < end)
//     {
//         int mid = (start + end) / 2;
//         mergesort(a, start, mid);
//         mergesort(a, mid + 1, end);
//         merge(a, start, mid, end);
//     }
// }
// int main()
// {
//     int n, i;
//     cout << "enter the number of elements you wanna take in array" << "\n";
//     cin >> n;
//     int a[n];
//     cout << "enter the elements of your array" << "\n";
//     for (int i = 0; i <= n - 1; i++)
//     {
//         cin >> a[i];
//     }
//     cout << "your array is" << "\n";
//     for (int i = 0; i <= n - 1; i++)
//     {
//         cout << a[i] << " ";
//     }
//     cout << "\n";
//     mergesort(a, 0, n - 1);
//     cout << "the sorted array is" << endl;
//     for ( int i = 0; i <= n - 1; i++)
//     {
//         cout << a[i] << " ";
//     }
//     cout << "\n";
//     return 0;
// }



///////////////////////////quicksort///////////////////////////
//////////////////////////////////////////////////////
//////////////partition///////////////////////////
int partition(int *a, int start, int end)
{
    int pivot = a[end], pindex = start, i;
    for (i = start; i < end; i++)
    {
        if (a[i] <= pivot)
        {
            swap(a[i], a[pindex]);
            pindex++;
        }
    }
    swap(a[end], a[pindex]);
    return pindex;
}

///////////////////////////recursive///////////////////////////
// void quicksort(int *a, int start, int end)
// {
//     if (start <= end)
//     {
//         int p = partition(a, start, end);//p ->correct index of a element
//         quicksort(a, start, p - 1);
//         quicksort(a, p + 1, end);
//     }
// }




///////////////////////////iterative quicksort///////////////////////////
// void iterativeQuickSort(int *a, int start, int end)
// {
//     stack<pair<int, int>> stk;
//     stk.push(make_pair(start, end));
//     while (stk.size() != 0)
//     {
//         start = stk.top().first, end = stk.top().second;
//         stk.pop();
//         int pivot = partition(a, start, end);
//         if (pivot - 1 > start) stk.push(make_pair(start, pivot - 1));
//         if (pivot + 1 < end)   stk.push(make_pair(pivot + 1, end));
//     }
// }

// int main()
// {
//     int n, i;
//     cout << "enter the number of elements you wanna take in array" << "\n";
//     cin >> n;
//     int a[n];
//     cout << "enter the elements of your array" << "\n";
//     for (int i = 0; i <= n - 1; i++)
//     {
//         cin >> a[i];
//     }
//     cout << "your array is" << "\n";
//     for (int i = 0; i <= n - 1; i++)
//     {
//         cout << a[i] << " ";
//     }
//     cout << "\n";
//     // quicksort(a, 0, n - 1);
//     iterativeQuickSort(a, 0, n - 1);
//     cout << "the sorted array is" << endl;
//     for ( int i = 0; i <= n - 1; i++)
//     {
//         cout << a[i] << " ";
//     }
//     cout << "\n";
//     return 0;
// }




///////////////////////////quickselect method///////////////////////////
///////////////////////////kth smallest element///////////////////////////
int main()
{
    int n, i, j, k;
    cin >> n >> k;
    k--;//k given 1 indexing ->0 indexing
    //initial k->3rd smallest===saying it as like 2nd index in array (0 indexing)
    int a[n];
    for (i = 0; i < n; i++) cin >> a[i];
    int start = 0, end = n - 1;
    if (k < start || k > end)
    {
        cout << "-1" << endl; return 0;
    }
    //edge cases
    while (1)//always true//infinite loop
        //start<=end
    {
        int p = partition(a, start, end);
        //0 indexing
        if (p == k)
        {
            cout << a[p] << endl; break;
        }
        if (p < k)
        {
            start = p + 1; continue;
        }
        else
        {
            end = p - 1; continue;
        }
    }
    return 0;
}