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

int fillArray(int**);

int findMinimum(int*, int);

int main(){
  int n, *clist, i;

  if ((n = fillArray(&clist)) > 0) { /* memory allocation ok */
    i = findMinimum(clist, n);  
    printf("Minimum is at position %d.\n", i);
    return 0;
    }
  else /* memory allocation failed */
    return 1;
}

/*
 * Prompt to enter the list's length and values.
 *  Parameters: *clist: pointer to an array of integers
 *  Returns: number of elements read
 */
int fillArray(int **clist) {
  int n, j;
  printf("How many values do you want to enter? ");
  scanf("%d", &n);

  /* Allocate memory */
  if ((*clist = (int*) malloc(n * sizeof(int))) > 0) { 
    /* Read values */
    for (j=0; j<n; j++){
      printf(" Value %d: ", j);
      scanf("%d", &((*clist)[j]));
    }
    return n;
  } else /* memory allocation failed */
    return -1;
}

/*
 * Use a variant of binary search to find the index of the minimal
 * element in a cyclically sorted array.
 *  Parameters: *clist: pointer to an array of integers
 *              n: size of list
 *  Returns: index i of minimal element
 */
int findMinimum(int *clist, int n){
  int left = 0, right = n-1, mid;
  /* while interval contains more than one element 
   * (least element is always between left and right) */
  while ((right - left) % n  > 0){
    mid = left + (right - left) / 2;
    if (clist[mid] <= clist[right])
      right = mid;
    else
      left = mid + 1;
  }
  return left;
}