Problem1533--来个板烧鸡腿堡吧!

1533: 来个板烧鸡腿堡吧!

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

众所周知,金拱门最好吃的汉堡就是板烧鸡腿堡。当然XP也是这么觉得的。

某个周末,XP到了一条金拱门街游玩,这条街上有n家金拱门的店铺,每个店铺都有一定的板烧鸡腿堡储量ai。现在,为了快乐,XP想在这条街道上买尽可能多的板烧鸡腿堡。但是,与此同时,出于某种汉堡哲学,当XP在第j个店铺买了xj个板烧鸡腿堡之后,必须保证在所有满足i>j的第i家店铺中都需要购买并且所买的板烧鸡腿堡的数量xi都大于xj 。

现在,XP给了你这些店铺的数量,和他们的板烧鸡腿堡储量,你可以帮他算出,他最多可以买多少的板烧鸡腿堡嘛?



Input

第一行给出一个整数n (1n2*105) ,代表这条街上的金拱门的数量 。
第二行给出n个整数 ai(1ai109) ,代表第i家金拱门店铺的板烧鸡腿堡储量 。

Output

输出XP所能买的最多的板烧鸡腿堡的数量。

Sample Input Copy

5
1 2 1 3 6

Sample Output Copy

10

Source/Category