Qabların yuyulması
Bessie və Elsie fermer John-a qabları yumaqda kömək edirlər. Barmaqları olmadığı üçün bu proses düşündüyünüzdən bir az daha çətindir.
İki inək qərara gəlib ki, Bessie sabun vuracaq, Elsie isə durulayacaq. Bessie-yə 1-dən n-ə qədər nömrələnmiş çirkli boşqablar yığını verilir. Elsie-nin isə təmiz boşqabları qoyacağı boş bir yığını var. Bessie və Elsie arasında sabunlu yığınlar üçün bir tezgah yerləşir.
Hər mərhələdə iki şeydən biri baş verir:
Bessie çirkli yığından bir boşqab götürür, ona sabun vurur və tezgaha qoyur. Sabunlu boşqabı tezgaha qoyarkən, Bessie ya (i) mövcud olan sabunlu yığının üstündəki boşqaba qoymalı, ya da (ii) mövcud olan sabunlu yığınların sağında yeni bir sabunlu yığın yaratmalıdır.
Elsie ən sol sabunlu yığının üstündən bir boşqab götürür. Elsie boşqabı durulayır və onu təmiz yığına qoyur.
Məqsəd, təmiz yığında bütün boşqabların ardıcıl şəkildə yerləşdirilməsidir: ən kiçik nömrəli boşqab altda, ən böyük nömrəli boşqab isə üstdə olmalıdır. İnəklər bu məqsədə bütün boşqab yığını üçün nail ola bilməzlər, buna görə də bu məqsədə nail olmaq mümkün olan giriş sırasının ən uzun prefiksinin uzunluğunu müəyyən edin.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) ədədini ehtiva edir. Növbəti n sətirdə Bessie yığınının üstündəki boşqabın nömrəsi ilə boşqabların sırası verilir.
Çıxış məlumatları
Giriş yığınının düzgün ardıcıllıqla təmiz yığında yerləşdirilə biləcəyi ən uzun prefiksinin uzunluğunu çıxış edin.