W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Pewnego dnia Bajtazar udał się na rynek w Bajtogrodzie, aby zagrać na bandżo. Żeby nie uprzykrzać zbytnio życia okolicznym mieszkańcom, postanowił, że zagra tylko dwie krótkie, jednominutowe piosenki. Mimo tego, Bajtazar bardzo chciał, by usłyszało go jak najwięcej osób. Zagrał więc jedną piosenkę, nieco odczekał, po czym zagrał drugą. Teraz zastanawia się, czy przypadkiem jego występu nie mogło usłyszeć więcej osób.
W ciągu dnia przez rynek przewinęło się osób, które będziemy numerować od do . Bajtazar dokładnie zapamiętał, kto i kiedy przyszedł na rynek. Osoba numer pojawiła się na rynku dokładnie na początku -tej minuty (licząc od świtu) i opuściła rynek na początku -tej minuty.
Bajtazar chciałby obliczyć, ile maksymalnie osób usłyszałoby jego granie, gdyby rozpoczynał występy w optymalnych momentach. Problem ten przerósł jednak jego umiejętności rachunkowe, gdyż dzień w Bajtocji trwa minut. Zrozpaczony Bajtazar poprosił Cię o pomoc.
Zakładamy, że Bajtazar gra dokładnie dwa razy, za każdym razem po jednej minucie. Każdy występ może się zacząć o dowolnej porze. W szczególności druga piosenka może rozpocząć się od razu po zakończeniu pierwszej. Dana osoba słyszy występ, jeśli znajduje się na rynku w trakcie całej minuty, podczas której Bajtazar gra.
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę osób, które przyszły na rynek w ciągu dnia. Każdy z kolejnych wierszy opisuje jedną z osób. W -tym z tych wierszy znajdują się dwie liczby całkowite oraz (), które oznaczają, że osoba numer przyszła na rynek na początku minuty , a poszła na początku minuty .
Twój program powinien wypisać na wyjście maksymalną liczbę różnych osób, które mogą usłyszeć występy Bajtazara na bandżo.
Dla danych wejściowych:
7 3 6 1 16 9 13 4 6 7 9 1 1 9 10
poprawną odpowiedzią jest:
5
Wyjaśnienie do przykładu: Bajtazar rozpoczyna pierwszą piosenkę w dowolnym momencie czwartej lub na początku piątej minuty. Pierwszą piosenkę słyszą więc osoby , i . Drugą piosenkę Bajtazar gra w dziewiątej minucie, gdy na rynku są osoby , i . Łącznie Bajtazara słyszy różnych osób.
Autor zadania: Jakub Łącki.