Складання Тарілок

Компанія Plate Shipping Company — це інтернет-ритейлер, що спеціалізується виключно на продажу тарілок. Вони пишаються тим, що пропонують найширший вибір обідніх тарілок у всесвіті від численних виробників.

У нещодавньому аналізі витрат компанія виявила, що витрачає значні кошти на пакування тарілок для відправки. Частково це пов'язано з тим, що тарілки потрібно складати перед тим, як помістити їх у контейнери для відправки. Це займає більше часу, ніж очікувалося. Можливо, ви можете допомогти.

Відправка тарілок складається з тарілок від кількох виробників. Тарілки від кожного виробника приходять складеними, тобто кожна розташована в одному стосі з тарілками, впорядкованими за розміром (найменша зверху, найбільша знизу). Ми будемо називати такий стос правильно впорядкованим. Щоб відправити всі ці тарілки, ви повинні об'єднати їх в один стос, знову правильно впорядкований. Щоб об'єднати стоси виробників в один стос, дозволено два види операцій:

• Розділити: один стос можна розділити на два стоси, піднявши будь-яку верхню частину стосу і відставивши її вбік, щоб утворити новий стос.

• Об'єднати: два стоси можна об'єднати, поставивши один на інший. Це дозволено лише в тому випадку, якщо нижня тарілка верхнього стосу не більша за верхню тарілку нижнього стосу, тобто об'єднаний стос має бути правильно впорядкованим.

Зверніть увагу, що частина будь-якого стосу ніколи не може бути безпосередньо поставлена на інший стос. Спочатку її потрібно розділити, а потім розділену частину потрібно об'єднати з іншим стосом. Дано колекцію стосів, ви повинні знайти мінімальну кількість операцій, які перетворять їх в один стос. Наступний приклад відповідає вхідним даним зразка і показує, як два стоси можуть бути перетворені в один стос за п'ять операцій: