/*
 * Michail Medvinsky
 * Quantiles alg.
 * 
 */

 #include <stdlib.h>
 #include <stdio.h>
 #include <memory.h>
 #include <fstream.h>

 #define D_LEFT 0
 #define D_RIGHT 1

 static int total_steps = 0;
 

 #define RAND_NUM srand(34763)

//#define STEP(x) total_steps += x;cout << "STEP("<< total_steps << ")" <<
endl
 #define STEP(x) total_steps += x
 #define INPUT_SZ 5000
 typedef struct bean_tag
 {
        int *list;
        int setMin;
        int setMax;
        int lastPos;    
 }qBean;

 typedef struct bean_coll_tag
 {
        qBean *beans;
        int depth;
        int num;
        int direct;
 }qBeanColl;


 void ordered_insert(qBeanColl *B, int pos, int num)
 {
        B->beans[pos].list[0] = num;
        if (pos == 0) return;

        for (int i = pos; i > 0; i--)
        {
                STEP(1);        
                if (B->beans[i - 1].list[0] > B->beans[i].list[0])
                {
                        int tmp = B->beans[i - 1].list[0];
                        B->beans[i - 1].list[0] = B->beans[i].list[0];
                        B->beans[i].list[0] = tmp;
                }
                else
                  break;
        }               
 }

 int randomized_init(int *A, int Asz, qBeanColl *B)
 {
        /*peek num random numbers from the Array A and insert-sort it into
the beans[i]->list[0]*/
        for (int i = 0; i < B->num; i++)
        {
                /*peek a random number */
                int rnum = RAND_NUM % Asz;
                rnum = (rnum == Asz ? rnum - 1 : rnum);
                /*assign the random number to the next top of the list of
the next bean*/
                ordered_insert(B, i, A[rnum]);
                /*swap this number with the last in the list and decrease
the number of entries in the A*/
                STEP(1);
                if (rnum < (Asz - 1))
                        A[rnum] = A[Asz - 1];
                Asz--;
        }
        return Asz;
 }

 qBeanColl *alloc_storage(int k, int depth)
 {
        qBeanColl *bc = new qBeanColl;
        bc->num = k;
        bc->depth = depth;
        bc->beans = new qBean[k];
        bc->direct = D_RIGHT;
                 
        for (int i = 0; i < k; i ++)
        {                 
                bc->beans[i].list = new int[depth];
                bc->beans[i].lastPos = 0;
                bc->beans[i].setMin = 0;
                bc->beans[i].setMax = 0;
                memset(bc->beans[i].list, 0, depth*sizeof(int));
        }
        return bc;
 }


 /*
  * find_location() method will do a search on the sorted
  *                 first row of the beans to find a place for this number
  */
  int find_location(qBeanColl *B, int lPart, int rPart, int num)
  {
        if (lPart == rPart)
                {
                        return rPart;
                }
        
        int lFrom = lPart;
        int lTo = lFrom + (rPart - lPart)/2;

        int rFrom = lTo + 1;
        int rTo = rPart;

        STEP(1);        
        if (B->beans[lTo].list[0] > num)
                return find_location(B, lFrom, lTo, num);       
        else
                return find_location(B, rFrom, rTo, num);       
        return -4;
  }
 

 /*find_max*/
 int find_max(int *list, int depth)
 {
        int mmax =  0;
        for (int i = 0; i < depth; i++)
        {
                STEP(1);        
                if (list[i] > list[mmax]) mmax = i;
        }
        return mmax;
 }

 /*find_min*/
 int find_min(int *list, int depth)
 {
        int mmin =  0;
        for (int i = 0; i < depth; i++)
        {
                STEP(1);        
                if (list[i] < list[mmin]) mmin = i;
        }
        return mmin;
 }


 void set_min_max(qBean *b, int depth)
 {
        int mIdx = 0;
        if (b->setMin == 1)
        {
                mIdx = find_min(b->list, depth);
                int swapk = b->list[mIdx];
                b->list[mIdx] = b->list[b->lastPos];
                b->list[b->lastPos] = swapk;
        }

        if (b->setMax == 1)
        {
                mIdx = find_max(b->list, depth);
                int swapk = b->list[mIdx];
                b->list[mIdx] = b->list[0];
                b->list[0] = swapk;
        }

        b->setMax = 0;
        b->setMin = 0;
 }


 void place_element(qBeanColl *B, int num, int posFound)
 {
        /*check to see if this bean still has space avaliabe*/
        STEP(1);        
        if (B->beans[posFound].lastPos < (B->depth - 1))
        {
                /*see if we need to replace the current maximum (0
position in a bean)*/
                STEP(1);        
                if (B->beans[posFound].list[0] < num)
                {

B->beans[posFound].list[++(B->beans[posFound].lastPos)] =
B->beans[posFound].list[B->beans[posFound].lastPos - 1];

B->beans[posFound].list[(B->beans[posFound].lastPos) - 1] =
B->beans[posFound].list[0];
                        B->beans[posFound].list[0] = num;
                        return;
                }

                /*compare the current minimum at the position lastPos with
A[i]*/
                STEP(1);
                if (B->beans[posFound].list[B->beans[posFound].lastPos] >
num)
                {

B->beans[posFound].list[++(B->beans[posFound].lastPos)] = num;
                }
                else
                {

B->beans[posFound].list[++(B->beans[posFound].lastPos)] =
B->beans[posFound].list[B->beans[posFound].lastPos - 1];

B->beans[posFound].list[(B->beans[posFound].lastPos) - 1] = num;
                }
                return;
        }

        /*if we are here then the bean is out of space*/

        STEP(1);
        if (posFound == (B->num - 1))
        { /*proccess the rightmost*/
                
                /*
                 * First: The maximum is exceding the maximum number
                 * just pop the current maximum and reporccess
                 */
                B->direct = D_LEFT;

                STEP(1);
                if (B->beans[posFound].list[0] < num)
                {
                        int cMax = B->beans[posFound].list[0];
                        B->beans[posFound].list[0] = num;
                        /*reset prev max*/
                        int pMax = B->beans[posFound - 1].list[0];
                        B->beans[posFound - 1].list[0] =
B->beans[posFound].list[B->beans[posFound].lastPos];                   

B->beans[posFound].list[B->beans[posFound].lastPos] = cMax;
                        B->beans[posFound].setMin = 1;
                        set_min_max(&(B->beans[posFound]), B->depth);
                        /*recursevly replace the prev max*/
                        place_element(B, pMax, posFound - 1);
                        return;
                }

                /*
                 * First: The number belongs in the maximum bean
                 * then make the minimum go back and put the number there
                 */
                STEP(1);
                if (B->beans[posFound].list[0] > num)
                {
                        int pMax = B->beans[posFound - 1].list[0];
                        B->beans[posFound - 1].list[0] =
B->beans[posFound].list[B->beans[posFound].lastPos];                   

B->beans[posFound].list[B->beans[posFound].lastPos] = num;
                        B->beans[posFound].setMin = 1;
                        set_min_max(&(B->beans[posFound]), B->depth);
                        /*recursevly replace the prev max*/
                        place_element(B, pMax, posFound - 1);
                        return;
                }
                return;
        }


        /*proccess to the right*/
        /*
         *      The minimum is smaller then the minimum here
         *  insert a new minimum, remove a maximum and make it a new
minimum in the next
         */
        if (posFound == 0)
        { 
                B->direct = D_RIGHT;
                STEP(1);
                if (B->beans[posFound].list[B->beans[posFound].lastPos] >
num)
                {
                        int cMax = B->beans[posFound].list[0];
                        B->beans[posFound].list[0] =
B->beans[posFound].list[B->beans[posFound].lastPos];

B->beans[posFound].list[B->beans[posFound].lastPos] = num;
                        int cMin = B->beans[posFound +
1].list[B->beans[posFound + 1].lastPos];
                        B->beans[posFound + 1].list[B->beans[posFound +
1].lastPos] = cMax;

                        B->beans[posFound].setMax = 1;
                        set_min_max(&(B->beans[posFound]), B->depth);
                
                        /*recursevly replace the prev min*/
                        place_element(B, cMin, posFound + 1);
                        return;
                }

                /*
                 *      The number belongs in this bean
                 *  Remove the maximum, then replace it forward and recalc
the minimum
                 */
                STEP(1);
                if (B->beans[posFound].list[B->beans[posFound].lastPos] <
num)
                {
                        int cMax = B->beans[posFound].list[0];
                        B->beans[posFound].list[0] = num;
                        int cMin = B->beans[posFound +
1].list[B->beans[posFound + 1].lastPos];
                        B->beans[posFound + 1].list[B->beans[posFound +
1].lastPos] = cMax;

                        B->beans[posFound].setMax = 1;
                        set_min_max(&(B->beans[posFound]), B->depth);                   
                        /*recursevly replace the prev min*/
                        place_element(B, cMin, posFound + 1);
                        return;
                }

        }

        STEP(1);
        if (B->direct == D_RIGHT)
        {
                STEP(1);
                if (B->beans[posFound].list[B->beans[posFound].lastPos] >
num)
                {
                        int cMax = B->beans[posFound].list[0];
                        B->beans[posFound].list[0] =
B->beans[posFound].list[B->beans[posFound].lastPos];

B->beans[posFound].list[B->beans[posFound].lastPos] = num;
                        int cMin = B->beans[posFound +
1].list[B->beans[posFound + 1].lastPos];
                        B->beans[posFound + 1].list[B->beans[posFound +
1].lastPos] = cMax;

                        B->beans[posFound].setMax = 1;
                        set_min_max(&(B->beans[posFound]), B->depth);
                
                        /*recursevly replace the prev min*/
                        place_element(B, cMin, posFound + 1);
                        return;
                }

                /*
                 *      The number belongs in this bean
                 *  Remove the maximum, then replace it forward and recalc
the minimum
                 */
                STEP(1);
                if (B->beans[posFound].list[B->beans[posFound].lastPos] <
num)
                {
                        int cMax = B->beans[posFound].list[0];
                        B->beans[posFound].list[0] = num;
                        int cMin = B->beans[posFound +
1].list[B->beans[posFound + 1].lastPos];
                        B->beans[posFound + 1].list[B->beans[posFound +
1].lastPos] = cMax;

                        B->beans[posFound].setMax = 1;
                        set_min_max(&(B->beans[posFound]), B->depth);                   
                        /*recursevly replace the prev min*/
                        place_element(B, cMin, posFound + 1);
                        return;
                }
        }
        else
        {
                STEP(1);
                if (B->beans[posFound].list[0] < num)
                {
                        int cMax = B->beans[posFound].list[0];
                        B->beans[posFound].list[0] = num;
                        /*reset prev max*/
                        int pMax = B->beans[posFound - 1].list[0];
                        B->beans[posFound - 1].list[0] =
B->beans[posFound].list[B->beans[posFound].lastPos];                   

B->beans[posFound].list[B->beans[posFound].lastPos] = cMax;
                        B->beans[posFound].setMin = 1;
                        set_min_max(&(B->beans[posFound]), B->depth);
                        /*recursevly replace the prev max*/
                        place_element(B, pMax, posFound - 1);
                        return;
                }

                /*
                 * First: The number belongs in the maximum bean
                 * then make the minimum go back and put the number there
                 */
                STEP(1);
                if (B->beans[posFound].list[0] > num)
                {
                        int pMax = B->beans[posFound - 1].list[0];
                        B->beans[posFound - 1].list[0] =
B->beans[posFound].list[B->beans[posFound].lastPos];                   

B->beans[posFound].list[B->beans[posFound].lastPos] = num;
                        B->beans[posFound].setMin = 1;
                        set_min_max(&(B->beans[posFound]), B->depth);
                        /*recursevly replace the prev max*/
                        place_element(B, pMax, posFound - 1);
                        return;
                }
                return;
        }

 } 

 /*find the quantiles for this collection*/
 qBeanColl *quantiles_finder(int *A, int Asz, int k)
 {
        if (k == 0)
                return NULL;
        qBeanColl *B = alloc_storage(k, Asz/k);
        Asz = randomized_init(A, Asz, B);
        for (int i = 0; i < Asz; i++)
        {
          /*find the bean into which the number should be put in*/
          int posFound = find_location(B, 0, B->num - 1, A[i]);
          place_element(B, A[i], posFound);
        }
        return B;
 }


 int main(int argc, char *argv[])
 {
        int InputArray[INPUT_SZ];
        int k = INPUT_SZ;
        int sz = INPUT_SZ;
        char buf[64];

        
        for (int i = 0; i <= INPUT_SZ; i++)
        {
                cin >> buf;
                if (INPUT_SZ == i)
                {
                        k = atoi(buf);
                }
                else
                        InputArray[i] = atoi(buf);
        } 
                
        
        qBeanColl *b = quantiles_finder(InputArray, sz, k);
        if (b == NULL)
        {
                printf("Not found\n");
                exit(0);
        }
/*      
        printf("\n");
        for (i = 0; i < b->depth; i++)
        {
                for (int j = 0; j < b->num; j++)
                {
                        printf("%d ", b->beans[j].list[i]);
                }
                printf("\n");
        }
*/
        printf("QUANTILES\n\n");
        for (i = 0; i < b->num; i++)
        {
                printf("%d\n", b->beans[i].list[0]);
        }

        printf("\n");
        printf("\n");
        printf("STEPS: %d for SIZEOF(%d) and QUANTILES(%d)\n",
total_steps, sz, k);
        return 0;
 }