Вы проходите стажировку в исследовательской группе по биоинформатике, изучающей ДНК. Одна цепочка ДНК состоит из множества генов, которые попадают в разные категории, называемые типами генов. Типы генов разграничены определенными последовательностями нуклеотидов, известными как генные маркеры. Каждый тип гена i имеет уникальный начальный маркер si и уникальный конечный маркер ei. После многих грязных работ (выращивания бактерий, извлечения клеток, создания белков и т. д.) Ваша исследовательская группа может преобразовать ДНК в форму, состоящую только из генных маркеров, удалив весь генетический материал, лежащий между маркерами.

Ваша исследовательская группа выдвинула интересную гипотезу о том, что интерпретация генов зависит от того, образуют ли маркеры некоторых типов генов правильно вложенные структуры. Чтобы решить, образуют ли маркеры типа i правильное вложение в заданную последовательность маркеров w, необходимо рассмотреть подпоследовательность w, содержащую только маркеры типа гена i (si и ei), не пропуская ни одного из них. Следующие (и только следующие) структуры считаются правильно вложенными:

• siei
• siNei, где N - правильно вложенная структура
• AB, где A и B - правильно вложенные структуры

Учитывая Ваш компьютерный опыт, Вам поручили исследовать это свойство, но есть еще одна сложность. Ваша группа изучает особый тип ДНК, называемый кольцевой ДНК, то есть ДНК, образующую замкнутую петлю. Для изучения вложенности в кольцевой ДНК необходимо разрезать петлю в каком-то месте, в результате чего получится уникальная последовательность маркеров (направление чтения фиксируется молекулярными свойствами). Формирует ли тип гена i правильное вложение, теперь также зависит от того, где разрезана кольцевая ДНК. Ваша задача состоит в том, чтобы найти место разреза, максимально увеличивающее число типов генов, образующих правильно вложенную структуру. На рисунке D.1 показан пример, соответствующий исходному образцу 1. Указанный разрез приводит к правильному вложению маркеров для типа гена 1.

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 106) - длину ДНК. Следующая строка содержит последовательность ДНК, то есть n маркеров. Каждый маркер представляет собой символ c, за которым следует целое число i, где c ∈ {s, e} указывает, является ли он начальным или конечным маркером. и i (1 ≤ i ≤ 106) представляет собой тип гена маркера. Данная последовательность ДНК была получена из кольцевой ДНК путем разрезания в произвольном месте.

Выходные данные

Выведите одну строку с двумя целыми числами p и m, где p - это позиция разреза, максимизирующая количество различных типов генов, образующих правильную вложенность, а m - это максимальное количество типов генов. ДНК разрезается непосредственно перед p-ым входным маркером (например, разрез, показанный на рисунке D.1, имеет p = 3). Если более чем одна позиция разрезания дает одно и то же максимальное значение m, выведите наименьшее p, которое дает это.