#1167. 制定价格

制定价格

题目描述

最近,一家网红旗帜商店出了一种营销策略,生意非常火爆,但是前来购买旗帜的客户也会对⽐价格,从⽽选择更优惠的产品。

⽬前有nn个客户前来购买旗帜,其中第ii名客户购买旗帜的最⾼预算为aia_i,如果旗帜的价格⼩于或等于aia_i,客户就会在这个店购买旗帜,反之不会购买旗帜。

⽼板请来了聪明的你,想请你帮他制定⼀个最合适的价格,使得他们商店的总收⼊最⾼。商店总收⼊是指购买旗帜

的⼈数乘以旗帜的价格(不是净收⼊)

输入格式

第⼀⾏,⼀个正整数nn,表示购买旗帜客户的⼈数。

第⼆⾏,nn个⽤空格隔开的正整数aia_i,分别表示每个客户的预算。

输出格式

共⼀⾏,⼀个整数,表示商店的最⼤收⼊。

样例

样例输入1

7
20 15 30 100 85 76 24

样例输出1

228

样例输入2

5
100 150 45 20 140

样例输出2

300

数据范围

对于50%50\%的数据满足,1n1031\le n \le 10^3

对于100%100\%的数据满足,1n1061\le n \le 10^61ai1061\le a_i\le 10^6

样例解释

对于样例1:制定价格为7676元时,赚的钱最多并且有33人购买,赚钱数为76×3=22876\times 3=228元。

对于样例2:制定价格为100100元时,赚的钱最多并且有33人购买,赚钱数为100×3=300100\times 3=300元。