Рядом с домом Монокарпа есть магазин, в котором продаются коллекционные фигурки. Скоро выйдет новый набор фигурок; в этом наборе содержится \(n\) фигурок, \(i\)-я фигурка стоит \(i\) монет и доступна для покупки с \(i\)-го дня по \(n\)-й день.
Для каждого из следующих \(n\) дней Монокарп знает, может ли он посетить магазин в этот день.
Каждый раз, когда Монокарп посещает магазин, он может купить любое количество фигурок, которые продаются в магазине (конечно, он не может купить фигурку, которая еще не доступна для покупки). Если Монокарп покупает хотя бы две фигурки в один день, он получает скидку, равную стоимости самой дорогой фигурки, которую он покупает (другими словами, он получает самую дорогую из фигурок, которые он покупает, бесплатно).
Монокарп хочет купить ровно одну \(1\)-ю фигурку, одну \(2\)-ю фигурку, ..., одну \(n\)-ю фигурку из набора. Он не может купить одну и ту же фигурку дважды. Какова минимальная сумма денег, которую он должен потратить?
Примечание
В первом наборе входных данных Монокарп покупает \(1\)-ю фигурку в \(1\)-й день и тратит \(1\) монету.
Во втором наборе входных данных Монокарп может купить \(1\)-ю и \(3\)-ю фигурки в \(3\)-й день, \(2\)-ю и \(4\)-ю фигурки в \(4\)-й день, а также \(5\)-ю и \(6\)-ю фигурки в \(6\)-й день. Тогда он потратит \(1+2+5=8\) монет.
В третьем наборе входных данных Монокарп может купить \(2\)-ю и \(3\)-ю фигурки в \(3\)-й день, а все остальные фигурки в \(7\)-й день. Тогда он потратит \(1+2+4+5+6 = 18\) монет.