#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LIM_LOW 10
#define LIM_HIGH 2000

#define REVERSE_POS 0
#define SORTED_POS 1

void bound(int* x, int l, int h) {
	if(*x > h)
		*x = h;
	if(*x < l)
		*x =  l;
}

int** cut(int* arr, int N, int k) {
	int** res = (int **) malloc(sizeof(int *) * 2);
	res[REVERSE_POS] = (int *) malloc(sizeof(int) * (N - k));
	res[SORTED_POS] = (int *) malloc(sizeof(int) * k);
	// copy sorted
	for(int i = 0; i < k; ++i)
		res[SORTED_POS][i] = arr[i];
	// reverse copy
	for(int i = 0; i < N - k; ++i) // if even we have overlap, so prevent it
		res[REVERSE_POS][i] = arr[N - i - 1];
	return res;
}

void dostuff(int* arr, int N) {
	int lower = 2, higher = N - 2;
	bound(&lower, 2, N);
	bound(&higher, 1, N - 2);
	int k = (rand() % (higher - lower) + lower);
	printf("Cutting at %d\n", k);
	int** partitioned = cut(arr, N, k);

	// edit our array
	for(int i = 0; i < N - k; ++i)
		arr[i] = partitioned[REVERSE_POS][i];
	for(int i = 0; i <= k; ++i)
		arr[N - k + i] = partitioned[SORTED_POS][i];
	for(int i = 0; i < 2; ++i)
		free(partitioned[i]);
	free(partitioned);
}

void show_arr(int* arr, int N) {
	for(int i = 0; i < N; ++i)
		printf("%d ", arr[i]);
}

void find_elem(int* arr, int N, int rank) {
	// find negative difference position
	int low, high;
	for(low = N - 2, high = N - 1; high < N && arr[high] - arr[low] >= 0; --low, --high);
	// high holds the beginning of sorted area, low holds end of reverse area
	printf("%d %d\n", low, high);
	int count = 0, temp = rank, pos = high;
	while(temp) {
		if(high < N)
			pos = high++;
		else if(low >= 0)
			pos = low--;
		++count;
		--temp;
	}
	printf("Element on rank %d is: %d", rank, arr[pos]);
}

int main() {
	srand(time(0));
	/*int N, *arr;
	printf("How many elements [%d .. %d]: ", LIM_LOW, LIM_HIGH);
	scanf("%d", &N);
	printf("%d Enter array elements...\n", N);
	bound(&N, LIM_LOW, LIM_HIGH);
	arr = (int *) malloc(sizeof(int) * N);
	for(int i = 0; i < N; ++i) {
		printf("a_%d: ", i);
		scanf("%d", &arr[i]);
	}*/
	int N = 12;
	int arr[] = { 2, 13, 22, 32, 41, 56, 77, 81, 99, 101, 232, 534 };
	dostuff(arr, N);
	show_arr(arr, N);
	int r;
	printf("\nEnter rank: ");
	scanf("%d", &r);
	bound(&r, 1, N);
	find_elem(arr, N, r);
	free(arr);
	return 0;
}