U377638 赚钱

小A很喜欢旅游，他的国家共有n个城市，编号依次为1到n，这个暑假小A打算从1号城市开始按编号从小到大依次旅游完所有的城市，最后达到n号城市，而且他不走回头路，每个城市只走一次。 小A很聪明，在没出发之前，他已经了解到，每个城市都有他喜欢的小熊纪念品，但是小A打算从经过的某一个城市x买一个纪念品，然后在后面经过的某个城市y卖掉，从而赚取一定的差价，但是他必须在某个城市买1次，而且只能买1个，并且一定要在后面的某个城市卖掉（不能在同一个城市先买入后再卖出），因为他家里已经有很多小熊纪念品了。 如，2 号城市的纪念品价格是 10 元，6 号城市的纪念品是 8 元，10 号城市的纪念品是 18元，假设小A在2号城市花10元钱买了一个纪念品，-2元），如果在10号城市卖，他就会赚8元。小 A 希望赚的钱越多越好。问：小A最多能赚多少钱（当然也有可能亏钱）？

无

无

样例1：在2号城市花1元买，在4号城市8元卖掉，赚7元。 样例2：在2号城市花8元买，在3号城市7元卖掉，赚-1元，即亏了1元。 【数据范围】 30%的数据：n