测试数据来自 system/1220

背景

每天中午的下课铃一响，浙江镇海中学的同学们都会冲出学校来附近的小饭馆吃饭，刹那间天昏地暗，飞砂走石，家家餐馆内都是一片黑压压的人 。馄饨店、饺子馆，在学校附近开一家红一家。身为镇海中学信息中心首席科学顾问兼资深信息学竞赛辅导老师Dennis看到了，他为了在业余时间方便学生，他租了学校附近的一家店面，雇了几个拉面师傅，开了一家“正宗兰州牛肉拉面馆”，生意还不错。

描述

由于经营管理的好，Dennis拉面店生意一天比一天火爆（他在全世界各地开设了分店，足迹遍布大江南北，并且曾经为了开设拉面店横渡太平洋）,Dennis一个人忙不过来了，于是他收了两个徒弟帮忙，大徒弟光光，小徒弟娃娃。有一天，Dennis把他们二人叫到跟前，交给他们一个密码锁盒，Dennis神情严肃地告诉他们这是宇宙超级无敌冲天乾坤五香霹雳拉面的精辟制作秘籍。若他们二人能打开此密码锁，便将这个前无古人后无来者放眼当今天下舍他无人知晓的独家秘籍传授给他们，从此他们便能在江湖上声名大噪，使宇宙超级无敌冲天乾坤五香霹雳拉面在宇宙各国畅销，屹立于拉面王国永远东方不败！光光和娃娃脑中顿时出现了家财万贯徒弟满门的景象，瞧，他俩眼都红了。

细瞧那密码锁，只见锁身上有一行多少不一的数字，还有一个数字拨盘。数字末尾留下了一个空格，光光和娃娃的脑中突然出现了小时侯经常玩的一个游戏：找规律。这个游戏就是给你一个数列的前几项，让你写出后一项，例如：
2 4 6 （8）
1 4 9 （16）
……
在开锁过程中，光光发现对于所有的问题，都可以用一种方法解决：对于一个已知前m项的数列a1,a2,a3……am,一定可以找到唯一的一个不超过m-1次的多项式f(x),使得f(1)=a1,f(2)=a2,f(3)=a3……f(m)=am,那么要找的下一项就是f(m+1)。例如上面的第一个数列根据前3个数可以写出唯一的通项公式：f(x)=2x，其中最高次项的次数为1，小于3。

光光和娃娃认为这个密码锁的打开方法便是如此。于是他们决定试试。

你是不是也蠢蠢欲动拉？那也一起来试试吧。

格式

输入格式

第一行是一个整数m,代表锁上有m个数字,m<=1000。

第二行有m个数字。输入的数字都是绝对值不超过10^9的整数。

输出格式

输出应该只有一行，为根据输入数据的规律推出的下一个数字，保证结果的绝对值都不大于10^9。

样例1

样例输入1

3
2 4 6

样例输出1

8

样例2

样例输入2

3
1 4 9

样例输出2

16

样例3

样例输入3

5
1 1 1 1 1

样例输出3

1

限制

共10点，每点1秒。

提示

30%的数据，m<=5
100%的数据，m<=1000

来源

fangyuhua&ycglovewxx