#include <stdio.h>
#include <math.h>
#include <limits.h>

int sCifara(int a){

	int zadnjaCifra, predzCifra, duzinaBroja=0, sumaC=0, kopija;
	int i=0;
	a=fabs(a);
	kopija=a;

	do{
		kopija=kopija/10;
		duzinaBroja++;
	}
	while(kopija!=0);


	for(i=0; i<duzinaBroja;i++){
		zadnjaCifra=a%10;
		sumaC=sumaC + zadnjaCifra;
		a=a/10;
	}

	return sumaC;
}


int fib(int poredi){
    int prvi, drugi, sljedeci, i=0;
    int sljedeci_broj, x, jeJednak=0;

    prvi=1;
    drugi=1;
    sljedeci=2;

    while(sljedeci<poredi){
        sljedeci=prvi+drugi;
        if(poredi==sljedeci) jeJednak=1;
        prvi=drugi;
        drugi=sljedeci;
    }

    if(jeJednak==1)return 1;
    else return 0;

}

void ubaci(int niz[],int duzinaNiza){
	int stvarnaDuzina= duzinaNiza*2;
	int i,pomocna;

	for(i=0;i<duzinaNiza-1;i++){
		niz[stvarnaDuzina-2-2*i]=niz[duzinaNiza-i-1];
	}
	for(i=1;i<=stvarnaDuzina;i++){
	pomocna=niz[i-1];

		if(i%2!=0){
			niz[i]=sCifara(pomocna);
		}
	}


}

int izbaci(int niz[], int duzinaNiza){
	int izbaciClan=0;
	int stvarnaDuzina= duzinaNiza;
	int i,j;
	int prvi, drugi, sljedeci, jeJednak=0;

	prvi=1;
    drugi=1;
    sljedeci=2;

	for(i=0;i<stvarnaDuzina;i++){

    if(niz[i]==1 || niz[i]==2){
    	jeJednak=1;
    	break;
    }

    while(sljedeci<niz[i]){
        sljedeci=prvi+drugi;
        if(niz[i]==sljedeci){ jeJednak=1; break;}
        prvi=drugi;
        drugi=sljedeci;
    }


	if(jeJednak==1){
			for(j=i;j<stvarnaDuzina-1;j++){
			niz[j]=niz[j+1];
			}
			stvarnaDuzina--;
			j--;
	}}

	return stvarnaDuzina;
}