#include <stdio.h>
#include <stdlib.h>
void sorting(int a[], int i) {
    int tmp = a[i];
    for(int j = i-1;j>=0;j--){
        if(a[j]>=tmp){
            a[j+1]=a[j];
            a[j]=tmp;
        }else{
            break;
        }
    }
}

int Fibonacci(int input[], int n){
    int max = input[n-1];
    int *output = (int*)malloc(n * sizeof(int));
    int FiNo[]={1,1};
    int tmp = 1;
    int j = 0;
    for(int i=0;i<max;i++){
        tmp = FiNo[0]+FiNo[1];
        FiNo[0] = FiNo[1];
        FiNo[1] = tmp;
        if(input[j]>=FiNo[0]&&input[j]<FiNo[1]){
            output[j] = FiNo[1];
            while(input[j]==input[j+1]){
                j++;
                output[j]=FiNo[1];
            }
            j++;
            if(j==n){
                return output;
            }
        }
    }

}

int main ()
{
  int n;
  printf ("Input the number of element(s) in the array:\n");
  scanf ("%d", &n);
  int *input = (int*)malloc(n * sizeof(int));
  printf ("Input the element(s) in the array:\n");
  scanf ("%d", &input[0]);
  for (int i = 1; i < n; i++){
    scanf ("%d", &input[i]);
    sorting(input,i);
  }
  printf ("The new sorting array is\n");
  for (int i = 0; i < n; i++){
      printf ("%d ", input[i]);
  }
  printf ("\n");
  printf ("The output is\n");
  int* output = Fibonacci(input,n);
  for (int i = 0; i < n; i++){
      printf ("%d ", output[i]);
  }

  return 0;
}