C. Мафи

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n$ хүн "мафи" тоглоомыг тоглохоор цугларав. Үе болгонд нэг нь зохицуулагч хийж бусад $n-1$ нь тоглоомонд оролцоно. Хүн болгон тоглоомын хэдэн үед нь зохицуулагч биш оролцож тоглохыг хүсэж байгаагаа хэлжээ. Бүх тоглогчийн хувьд хүссэн тооноос нь багагүйгээр оролцогч байлгаж болох хамгийн бага тоглолтын үеийн тоог ол.

Оролт

Эхний мөрөнд $n$ тоо ($3 ≤ n ≤ 10^5$). Хоёр дахь мөрөнд $n$ ширхэг тоо $a_1$, $a_2$, ... , $a_n$ ($1 ≤ a_i ≤ 10^9$) байрлана. $a_i$ нь $i$ дахь тоглогчийн хамгийн багадаа оролцогч байж үзэхийг хүсэж байгаа үеийн тоо.

Гаралт

Нэг мөрөнд хүн бүрийг ядаж $a_i$ удаа оролцуулахын тулд хамгийн багадаа шаардагдах тоглолтын тоо.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
3
3 2 2
Гаралт
4
Оролт
4
2 2 2 2
Гаралт
3

Тэмдэглэл

You don't need to know the rules of "Mafia" to solve this problem. If you're curious, it's a game Russia got from the Soviet times: http://en.wikipedia.org/wiki/Mafia_(party_game)$.

Сэтгэгдлүүдийг ачааллаж байна...