Кільцева ДНК
Ви проходите стажування в дослідницькій групі з біоінформатики, яка вивчає ДНК. Один ланцюг ДНК складається з багатьох генів, що належать до різних категорій, званих типами генів. Типи генів розмежовані певними послідовностями нуклеотидів, відомими як генні маркери. Кожен тип гена i має унікальний початковий маркер s[i] і унікальний кінцевий маркер e[i]. Після багатьох лабораторних робіт (вирощування бактерій, вилучення клітин, створення білків тощо) ваша дослідницька група може перетворити ДНК у форму, що складається лише з генних маркерів, видаливши весь генетичний матеріал між маркерами.
Ваша дослідницька група висунула цікаву гіпотезу про те, що інтерпретація генів залежить від того, чи утворюють маркери деяких типів генів правильно вкладені структури. Щоб визначити, чи утворюють маркери типу i правильне вкладення в заданій послідовності маркерів w, необхідно розглянути підпослідовність w, що містить лише маркери типу гена i (s[i] і e[i]), не пропускаючи жодного з них. Наступні (і тільки наступні) структури вважаються правильно вкладеними:
s[i]e[i]s[i]Ne[i], де N - правильно вкладена структураAB, де A і B - правильно вкладені структури
Зважаючи на ваш комп'ютерний досвід, вам доручили дослідити цю властивість, але є ще одна складність. Ваша група вивчає особливий тип ДНК, званий кільцевою ДНК, тобто ДНК, що утворює замкнуту петлю. Для вивчення вкладеності в кільцевій ДНК необхідно розрізати петлю в якомусь місці, в результаті чого вийде унікальна послідовність маркерів (напрямок читання фіксується молекулярними властивостями). Чи утворює тип гена i правильне вкладення, тепер також залежить від того, де розрізана кільцева ДНК. Ваше завдання полягає в тому, щоб знайти місце розрізу, яке максимально збільшує число типів генів, що утворюють правильно вкладену структуру. На рисунку D.1 показано приклад, що відповідає вихідному зразку 1. Зазначений розріз призводить до правильного вкладення маркерів для типу гена 1.
Вхідні дані
Перший рядок містить ціле число n (1 ≤ n ≤ 10^6) - довжину ДНК. Наступний рядок містить послідовність ДНК, тобто n маркерів. Кожен маркер представляє собою символ c, за яким слідує ціле число i, де c ∈ {s, e} вказує, чи є він початковим або кінцевим маркером, і i (1 ≤ i ≤ 10^6) представляє тип гена маркера. Дана послідовність ДНК була отримана з кільцевої ДНК шляхом розрізання в довільному місці.
Вихідні дані
Виведіть один рядок з двома цілими числами p і m, де p - це позиція розрізу, що максимізує кількість різних типів генів, що утворюють правильну вкладеність, а m - це максимальна кількість типів генів. ДНК розрізається безпосередньо перед p-им вхідним маркером (наприклад, розріз, показаний на рисунку D.1, має p = 3). Якщо більше ніж одна позиція розрізу дає те саме максимальне значення m, виведіть найменше p, яке дає це.