CF853D.Michael and Charging Stations

Michael has just bought a new electric car for moving across city. Michael does not like to overwork, so each day he drives to only one of two his jobs.

Michael's day starts from charging his electric car for getting to the work and back. He spends 1000 burles on charge if he goes to the first job, and 2000 burles if he goes to the second job.

On a charging station he uses there is a loyalty program that involves bonus cards. Bonus card may have some non-negative amount of bonus burles. Each time customer is going to buy something for the price of x burles, he is allowed to pay an amount of y (0 ≤ y ≤ x) burles that does not exceed the bonus card balance with bonus burles. In this case he pays x - y burles with cash, and the balance on the bonus card is decreased by y bonus burles.

If customer pays whole price with cash (i.e., y = 0) then 10% of price is returned back to the bonus card. This means that bonus card balance increases by bonus burles. Initially the bonus card balance is equal to 0 bonus burles.

Michael has planned next n days and he knows how much does the charge cost on each of those days. Help Michael determine the minimum amount of burles in cash he has to spend with optimal use of bonus card. Assume that Michael is able to cover any part of the price with cash in any day. It is not necessary to spend all bonus burles at the end of the given period.

迈克尔刚刚购买了一辆新的电动汽车，用于在城市中通勤。迈克尔不喜欢过度劳累，因此他每天只去两份工作中的其中一份。

迈克尔的每一天都从为电动汽车充电开始，以便往返于工作地点之间。若他前往第一份工作，则充电花费 1000 卢布；若前往第二份工作，则充电花费 2000 卢布。

他所使用的充电站提供一项忠诚度计划，该计划包含一张积分卡。积分卡上可持有若干非负数量的积分卢布。每当顾客准备以 x 卢布的价格购买某商品时，他可选择用积分卢布支付其中一部分金额 y（满足 0 ≤ y ≤ x），且 y 不得超过积分卡当前余额。此时，他需用现金支付 x − y 卢布，同时积分卡余额减少 y 积分卢布。

若顾客完全使用现金支付全部价格（即 y = 0），则将有价格的 10% 返还至积分卡中。这意味着积分卡余额增加 积分卢布。初始时，积分卡余额为 0 积分卢布。

迈克尔已规划好接下来的 n 天，并且知道每一天的充电费用。请帮助迈克尔计算：在最优使用积分卡的前提下，他所需支付的最少现金总额（单位：卢布）。假设迈克尔在任意一天均可自由决定用现金支付价格的任意部分。在给定时间段结束时，不必耗尽全部积分卢布。

The first line of input contains a single integer n (1 ≤ n ≤ 300 000), the number of days Michael has planned.

Next line contains n integers _a_1, _a_2, ..., a__n (a__i = 1000 or a__i = 2000) with a__i denoting the charging cost at the day i.

输入的第一行包含一个整数 $n$（$1 ≤ n ≤ 300\,000$），表示 Michael 已规划的天数。

下一行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（其中每个 $a_i = 1000$ 或 $a_i = 2000$），$a_i$ 表示第 $i$ 天的充电费用。

Output the minimum amount of burles Michael has to spend.

输出迈克尔需要花费的最少 burles 数量。

In the first sample case the most optimal way for Michael is to pay for the first two days spending 3000 burles and get 300 bonus burles as return. After that he is able to pay only 700 burles for the third days, covering the rest of the price with bonus burles.

In the second sample case the most optimal way for Michael is to pay the whole price for the first five days, getting 1000 bonus burles as return and being able to use them on the last day without paying anything in cash.

在第一个样例中，迈克尔的最优策略是为前两天付费，共花费 3000 卢布，并获得 300 卢布的返利奖金。之后，他只需为第三天支付 700 卢布，剩余费用用奖金支付。

在第二个样例中，迈克尔的最优策略是为前五天全额付费，获得 1000 卢布的返利奖金，从而在最后一天无需现金支付即可完成消费。