著名的股票经纪人 Gina Reed 在工作中度过了平淡的一天，在几轮纸牌游戏之间，她开始做白日梦。预知未来很难，但试想一下，如果你能回到过去，利用你对股票价格历史的了解来最大化你的利润！

现在 Gina 开始思考：如果她能回到过去几天，并随身携带 100 美元，通过在合适的时机买卖 Rollercoaster Inc.（现存最不稳定的股票）的股票，她能赚多少钱？她能赚到足够的钱在特内里费岛的豪宅中舒适地退休吗？

请注意，Gina 不能购买零碎的股票，她必须购买 Rollercoaster Inc. 的整数股。Rollercoaster Inc. 的股票总数为 100 000 股，因此 Gina 在任何时候持有的股票都不能超过 100 000 股。在 Gina 的白日梦中，世界是美好而简单的：买卖股票没有手续费，股票价格每天只变动一次，且她的交易不会影响股票的估值。

Photo by liz west on flickr, cc by

输入格式

第一行包含一个整数 $d$ ($1 \le d \le 365$)，表示 Gina 在白日梦中回到过去的天数。接下来有 $d$ 行，第 $i$ 行包含一个整数 $p_i$ ($1 \le p_i \le 500$)，表示 Gina 在第 $i$ 天买入或卖出 Rollercoaster Inc. 股票的价格。日期按从旧到新的顺序排列。

输出格式

输出 Gina 在最后一天可能拥有的最大金额。注意，答案可能超过 $2^{32}$。

样例

样例输入 1

6
100
200
100
150
125
300

样例输出 1

650