/*
斐波那契查找的主要思想是：
利用斐波那契数列进行下表分割。
F(k)=F(k-1)+F(k-2)
那么：
F(k)-1=F[k-1]-1+F[k-2]
也即有：
F[k]-1=F[k-1]-1+1(mid,中间数)+F[k-2]-1;
*/
#include<cstdio>
#define MAX 1000

int F[]={0,1,1,2,3,5,8,13,21,34};//全局数组

int Fibonacci_Search(int *a,int n,int key)
{
	int low,mid,high,i,k;
	low=1;
	high=n;
	k=0;
	while(n>F[k])//计算n位于斐波那契数列的位置
		k++;
	for(i=n;i<F[k]-1;i++)//将不满的数值补上
		a[i]=a[n];
	while(low<=high)
	{
		mid=low+F[k]-1;//当前分割下标
		if(key<a[mid])
		{
			high=mid-1;
			k=k-1;
		}
		else if(key>a[mid])
		{
			low=mid+1;
			k=k-2;
		}
		else
		{
			if(mid<=n)
				return mid;//mid即为找到的位置
			else 
				return n;//说明是补全的数值，返回n
		}
	}
	return 0;
}

int main(int argc,char *argv[])
{
	int Array[MAX];
	int n,key;
	int i,index;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&Array[i]);
	scanf("%d",&key);
	index=Fibonacci_Search(Array,n,key);
	if(index==n||index==0)
		printf("Can not find!\n");
	else
		printf("Find it,index is: %d\n",index);
	
	return 0;
}