// Partitioning to find k largest elements
// See CLRS for details
#include <stdio.h>

int *arr;
int arrSize;

int newPartition(int *arr,int p,int r)
// From CLRS, 2nd ed.
{
int x,i,j,temp;

/*
printf("Input\n");
for (i=p;i<=r;i++)
  printf("%d %d\n",i,arr[i]);
*/

x=arr[r];
i=p-1;
for (j=p;j<r;j++)
  if (arr[j]<=x)
  {
    i++;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
  }
temp=arr[i+1];
arr[i+1]=arr[r];
arr[r]=temp;
/*
printf("Left output\n");
for (j=p;j<=i;j++)
  printf("%d %d\n",j,arr[j]);
printf("In final position\n");
printf("%d %d\n",i+1,arr[i+1]);
printf("Right output\n");
for (j=i+2;j<=r;j++)
  printf("%d %d\n",j,arr[j]);
*/
return i+1;
}

newQuickSort(int *a,int p,int r)
{
int q;

if (p<r)
{
  q=newPartition(a,p,r);
  newQuickSort(a,p,q-1);
  newQuickSort(a,q+1,r);
}
}

newSelect(int *a, int low, int high, int numElements)
{
int q;

while (1)
{
  printf("low %d high %d numElements %d\n",low,high,numElements);
  if (high-low+1<=numElements)
    return;
  q=newPartition(a,low,high);
  printf("q %d\n",q);
  if (high-q+1==numElements)
  {
    printf("Case 1\n");
    return;
  }
  if (high-(q+1)+1==numElements)
  {
    printf("Case 2\n");
    return;
  }
  if (high-q+1<numElements)
  {
    printf("Case 3\n");
    numElements-=high-q+1;
    high=q-1;
    printf("numElements is now %d\n",numElements);
  }
  else // high-q+1>numElements
  {
    printf("Case 4\n");
    low=q+1; 
  }
}
}

main()
{
int i,k;
unsigned seed;

scanf("%d",&arrSize);
arr=(int*) malloc(sizeof(int)*arrSize);
if (!arr)
{
  printf("malloc failed\n");
  abort();
}
scanf("%d",&k);
for (i=0;i<arrSize;i++)
  scanf("%d",&arr[i]);
//newQuickSort(arr,0,arrSize-1);
for (i=0;i<arrSize;i++)
  printf("%d %d\n",i,arr[i]);
printf("----------------\n");
printf("----------------\n");
newSelect(arr,0,arrSize-1,k);
for (i=0;i<arrSize-k;i++)
  printf("%d %d\n",i,arr[i]);
printf("----------------\n");
for (i=arrSize-k;i<arrSize;i++)
  printf("%d %d\n",i,arr[i]);
}