Яхуб допомагає дідові на фермі. Сьогодні треба доїти корів. Перед Яхубом вишикувалися в ряд n корів, пронумерованих від 1 до n зліва направо. Кожна корова дивиться або наліво, або направо. Коли Яхуб доїть корову, всі інші корови, які це бачать, лякаються і втрачають одну одиницю молока у вимені. Якщо корова дивиться наліво, то вона бачить всіх корів з номерами менше її номера. Якщо ж корова дивиться направо, то вона бачить всіх корів з номерами більше її номера. Корова, яка налякалася одного разу, може злякатися ще раз (і втратити ще одну одиницю молока). Якщо корову вже подоїли один раз, то вона більше не лякається і не втрачає молоко. Передбачається, що корова ніколи не втрачає все молоко, що у неї є (у корови в вимені нескінченну кількість молока).
Яхуб може визначити порядок, в якому він доїть корів. Проте він зобов'язаний подоїти кожну корову рівно один раз. Яхуб хоче втратити якомога менше молока. Виведіть найменшу кількість молока, яке він може втратити.
Виведіть єдине ціле число, мінімальна кількість втраченого молока.
Будь ласка, не використовуйте специфікатор% lld для читання і запису 64 бітних цілих чисел на С ++. Рекомендується використовувати потоки cin. cout або специфікатор% I64d.
→ Віртуальне участь
→ Теги завдання
Немає прав на редагування
→ Матеріали змагання
- Анонс
Змагання з програмування 2.0
Мобільна версія, переключитися на десктопну.