Famozni Faraon
시간 제한1초메모리 제한1024 MB
한 플레이어의 카드 순서와 나머지 카드가 주어질 때, 더 높은 카드가 이기는 규칙을 한 번 낮은 카드가 이기는 규칙으로 바꿀 수 있을 때 두 번째 플레이어가 이길 수 있는 최대 라운드 수를 구한다.
문제
Vitić-oh je jedini živi potomak famaznog faraona Yu-gi-oh-a. Po uzoru na svoje pretke, on još od malih nogu izučava kartaške igre. Njegova neosporiva nadmoć i dominacija u svakoj igri rezultirala je time da se naš junak previše opustio i treninge zamjenio razonodom.
Njegovoj idili došao je kraj kad je prije tjedan dana naletio na svoju polusestru Paulu-oh koja se do tad skrivala u sjenkama i čekala svoju priliku.
Okršaj generacije na rasporedu je sljedeći tjedan na Wembley-u. Igrat će se s 2n karata. Svaka karta ima svoju jedinstvenu oznaku od 1 do 2n. Oba junaka dobila su po n karata. Okršaj se odvija u n rundi. U svakoj rundi oba igrača odigravaju jednu od svojih preostalih karata te onaj igrač koji odigra kartu sa većom oznakom osvaja tu rundu. Na ovaj način svaka karta bit će odigrana u točno jednoj rundi.
Vitić-oh želi osigurati pobjedu i očuvati ugled pa se odlučio okrenuti svojoj najizučavanijoj strategiji - varanju. Uposlio je doušnike da saznaju Paula-oh-inu strategiju te je prije igre uspio otkriti redoslijed karata koje će ona odigravati.
Kao kralj karata, Vitić-oh također ima pravo jednom u okršaju promjeniti pravila igre tako da od tog trenutka nadalje runde pobjeđuje karta s manjom oznakom. Ovu opciju Vitić-oh ne mora uopće iskoristiti, a može je iskoristiti i prije prve runde.
Za zadanu raspodjelu karata igračima i redosljed kojim će Paula-oh odigravati karte u rundama pomognite Vitić-ohu da pobjedi najveći mogući broj rundi.
입력
U prvom retku nalazi se prirodan broj n (1 ≤ n ≤ 50 000) iz teksta zadatka.
U sljedećih n redaka nalazi se po jedan prirodan broj. Ti brojevi opisuju redoslijed karata koje će Paula-oh odigrati.
Vitić-oh na raspolaganju ima preostale karte.
출력
U jedini redak ispišite maksimalan broj rundi koje Vitić-oh može pobjediti.