Kibrit qutusu
Dostikdəki qız Tanya, Test-the-Best oyunçularının köməyi ilə ev tapşırığını yerinə yetirmək üçün neçə qutuya ehtiyacı olduğunu hesablaya bildi. Amma kiçik qardaşı Pyotr gəldi və bəzi kibritləri masanın üzərinə sıra ilə düzdü. İndi Tanya onu cəzalandırmaq istəyir - qardaşını kibritləri yenidən qutulara yığmağa məcbur etmək istəyir. Tanya kaprizlidir və qardaşının yalnız X ilə Y arasında olan kibritləri (kibritlər soldan sağa doğru sıfırdan başlayaraq ardıcıl tam ədədlərlə nömrələnir) yığmasını istəyir, qalan kibritləri isə Tanya əvvəlcədən masadan yerə atacaq (Tanyanın hərəkətlərinə atasının reaksiyası məsələnin şərtində qeyd olunmur :) ).
Tanya həmçinin Pyotrun kibritləri hansı qaydada və nə qədər götürməli olduğu barədə ciddi şərtlər qoymaq istəyir. Bu şərtlər belədir: qardaş bir dəfəyə mümkün qədər çox ardıcıl və eyni uzunluqda olan kibritləri götürməlidir, onların arasında ən kiçik nömrəli kibrit olmalıdır.
Nədənsə Tanya Pyotrun kibritləri yığarkən bir dəfəyə masadan götürəcəyi maksimum kibrit sayını maraqlanır. Bu dəyəri hesablamağı sizdən xahiş etdi. Tanya X və Y dəyərləri ilə hələ dəqiq qərar vermədiyi üçün, hesablamaları bir neçə cüt (X, Y) üçün dərhal etmək lazımdır.
Giriş verilənləri
Birinci sətir masanın üzərində olan kibritlərin uzunluqlarını soldan sağa doğru təyin edir. Bu sətirin hər bir simvolu '1'..'9' rəqəmi olub, müvafiq kibritin uzunluğunu müəyyən edir. Sətir 1 ilə 100000 arasında simvol ehtiva edir.
İkinci sətir Tanya üçün maraqlı olan dəyəri hesablamaq lazım olan (X, Y) cütlərinin boşluqla ayrılmış siyahısını ehtiva edir. Hər bir cüt "(X, Y)" şəklində təsvir olunur. Sətir 1 ilə 10000 arasında cüt ehtiva edir.
Çıxış verilənləri
İkinci sətirdə verilmiş hər bir (X, Y) cütü üçün qardaşın bir dəfəyə masadan götürəcəyi maksimum kibrit sayını tapın. Son sətirdəki rəqəmlərin sırası ikinci sətirdəki cütlərin sırasına uyğun olmalıdır, rəqəmlər tək boşluqla ayrılmalıdır - çıxış məlumatlarının nümunəsinə baxın.
Nümunələrə izah
Nümunə 1
Bütün 4 halda Pyotr bir dəfəyə masadan bütün kibritləri götürə biləcək.
Nümunə 2
Bütün 4 halda Pyotr həmişə bir dəfəyə masadan bir kibrit götürəcək.
Nümunə 3
1-ci hal: X=1, Y=5. Pyotrun qarşısında {2, 3, 3, 3, 4} kibritləri qalacaq. Əvvəlcə bir ədəd uzunluğu 2 olan kibrit götürəcək, sonra 3 ədəd uzunluğu 3 olan kibrit və nəhayət bir ədəd uzunluğu 4 olan kibrit götürəcək. Bir dəfəyə götürülən maksimum kibrit sayı - 3.
2-ci hal: X=0, Y=13. Pyotrun qarşısında bütün kibritlər qalacaq. 5-ci addımda 4 ədəd uzunluğu 2 olan kibrit götürəcək.
3-cü hal: X=2, Y=7. Pyotrun qarşısında {3, 3, 3, 4, 2, 2} kibritləri qalacaq. Və yəqin ki, artıq özünüz də təxmin etdiniz, əvvəlcə 3 ədəd uzunluğu 3 olan kibrit götürəcək, sonra bir ədəd uzunluğu 4 olan kibrit və sonda qalan 2 ədəd uzunluğu 2 olan kibrit götürəcək.