B. Мангас ба Хэрэм

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

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

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

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

Нарны туяа тусмагц Ари мангас босдог ба тэрээр юун түрүүнд хэрмээ хооллодог.

Ари энгийн гүдгэр олон өнцөгт зураад, оройнуудыг нь цагийн зүүний дагуу $1, 2, ..., n$ гэж дугаарлана. Тэгээд $1$ дугаартай оройноос эхлэн бусад оройнууд руу шулуун татдаг. Буцаад орой дээрээ ирэх эсвэл өмнө зурсан шулуунтай огтлолцох тохиолдолд шулуун зурахаа зогсооно. Ари энэ үйлдлээ бусад $2, 3, ..., n$ (уг дарааллаар) дугаартай оройнуудад ч мөн давтана. Дараа нь олон өнцөгт доторх хэсэг бүрт самар тавина.

Ада хэрэм бүх самрыг цуглуулах хүсэлтэй. Гэхдээ тэр Аригийн зурсан шулуун дээр зогсож болохгүй. Энэ нь Ада нэг хэсгээс нөгөө рүү явахыг хүсвэл жижиг үсрэлт л хийнэ гэсэн үг юм. Ада P хэсгээс Q хэсэг рүү үсрэхийн тулд P ба Q хэсгүүд нь нэг тал эсвэл нэг булангаар холбогдсон байх ёстой.

Адаг зургийн гадна талаас эхэлнэ гэж үзвэл бүх самрыг цуглуулахад хамгийн багадаа хэдэн үсрэлт хийх вэ?

Оролт

Оролтын мөр нь Аригийн зурах энгийн олон өнцөгтийн оройны тоог харуулах нэг бүхэл тоо $n$ ($3 ≤ n ≤ 54321$) агуулна.

Гаралт

Бүх самрыг цуглуулахын тулд Адагийн хийж болох хамгийн бага үсрэлтийн тоог хэвлээрэй. Үүний дараа тэр олон өнцөгтийг орхих шаардлагагүй гэдгийг анхаараарай.

Орчуулсан: Солонго

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

Оролт
5
Гаралт
9
Оролт
3
Гаралт
1

Тэмдэглэл

Эхний жишээн дэх боломжит шийдлүүдийн нэг нь дээрх зурагт харагдаж байна.

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