კუნძების აფეთქება

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2005/06, JAN, BRONZE


ძროხებზე გამუდმებით მზრუნველმა ფერმერმა ჯონიმ გადაწყვიტა ააფეთქოს საძოვარზე განლაგებული N (1 <= N <= 50,000) ცალი კუნძი. კუნძები განლაგებული არიან ერთ მწკრივად და გადანომრილია 1–დან N–მდე. თითოეულ კუნძს გააჩნია სიმაღლე H_i (1 <= H_i<= 10,000).

ჯონი იყენებს ტრადიციულ ასაფეთქებელ ნივთიერებას, რომელსაც შეუძლია ააფეთქოს არა მარტო უშუალოდ ის კუნძი, სადაც ასაფეთქებელი დევს, არამედ მეზობელი კუნძებიც, თუმცა მეზობელი კუნძების აფეთქება მხოლოდ მაშინ არის შესაძლებელი, როცა მათი სიმაღლე მკაცრად ნაკლებია უშუალოდ მათ გვერდით მდებარე აფეთქებულ კუნძზე. სხვაგვარად რომ ვთქვათ, ერთი ანადგურებს კუნძებს მარჯვნივ ან მარცხნივ მანამ, ვიდრე მორიგი აფეთქებული კუნძის მეზობლად მასზე არანაკლები სიმაღლის კუნძი არ აღმოჩნდება.

განვიხილოთ კუნძების მწკრივი შემდეგი სიმაღლეებით:

              1 2 5 4 3 3 6 6 2

თუ ფჯ ააფეთქებს მესამე კუნძს (სიმაღლით 5), მარცხენა მხარეს მასთან ერთად აფეთქდება მეორე კუნძიც (სიმაღლით 2) და პირველი კუნძიც (სიმაღლით 1), ხოლო მარჯვენა მხარეს აფეთქდება მეოთხე (სიმაღლით 4) და მეხუთე (სიმაღლით 3) კუნძებიც. რადგან მეექვსე კუნძის სიმაღლე მეხუთეს ტოლია, აფეთქება მასზე არ გავრცლდება. პირველი აფეთქების მერე გვექნება სიტუაცია:

              * * * * * 3 6 6 2

კიდევ ორი აფეთქებით (მეშვიდე და მერვე კუნძები) კუნძები მთლიანად განადგურდება.

დაეხმარეთ ფჯ–ს მინიმალური რაოდენობის აფეთქებებით კუნძების განადგურებაში.

შესატანი მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი N. მომდევნო N სტრიქონიდან თითოეულში თითო მთელი რიცხვი – H_i.

გამოსატანი მონაცემები: თითო სტრიქონში თითო მთელი რიცხვი – ასაფეთქებელი კუნძების ნომრები. რიცხვები დალაგებული უნდა იყოს ზრდადობით.




მაგალითები

შესატანი მონაცემები
9 1 2 5 4 3 3 6 6 2 დაკოპირება
გამოსატანი მონაცემები
3 7 8 დაკოპირება