由于经营管理的好，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：
3
2 4 6
样例2：
3
1 4 9
样例3：
5
1 1 1 1 1

样例1
8
样例2
16
样例3
1