D. Игра в теннис
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Петя и Гена любят играть в настольный теннис. Игра идет по следующим правилам: партия состоит из нескольких сетов, каждый сет состоит из нескольких розыгрышей. Каждый из розыгрышей выигрывает один из игроков, ему присуждается одно очко. Как только один из игроков набирает t очков, ему присуждается победа в сете; после этого начинается следующий сет и счет выигранных розыгрышей обоих игроков обнуляется. Как только один из игроков выигрывает в сумме s сетов, ему присуждается победа в партии и игра заканчивается. Здесь s и t — некоторые целые положительные числа.

Чтобы разнообразить игру, Петя и Гена выбирают новые числа s и t перед каждой партией. Кроме этого, для истории ход каждой партии записывается: для каждого розыгрыша указывается, кто его выиграл. Розыгрыши записываются в хронологическом порядке. В записи партии сет завершается, как только один из игроков набрал t очков, и партия завершается, как только один из игроков выиграл s сетов.

Петя и Гена нашли запись старой партии. К сожалению, последовательность розыгрышей в записи не разделена на сеты, и числа s и t для данной партии тоже утеряны. Теперь игрокам интересно, чему могли быть равны s и t. Сможете ли вы определить все возможные варианты?

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

В первой строке записано одно целое число n — длина последовательности розыгрышей (1 ≤ n ≤ 105).

Во второй строке записаны n целых чисел ai, разделенных пробелами. Если ai = 1, то i-ю подачу выиграл Петя, если ai = 2, то i-ю подачу выиграл Гена.

Не гарантируется, что записи соответствует хотя бы один вариант чисел s и t.

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

В первой строке выведите одно число k — количество вариантов для чисел s и t.

В каждой из следующих k строк выведите по два числа si и ti — очередной вариант для чисел s и t. Варианты следует выводить в порядке возрастания si, а при равенстве si — в порядке возрастания ti.

Примеры
Входные данные
5
1 2 1 2 1
Выходные данные
2
1 3
3 1
Входные данные
4
1 1 1 1
Выходные данные
3
1 4
2 2
4 1
Входные данные
4
1 2 1 2
Выходные данные
0
Входные данные
8
2 1 2 1 1 1 1 1
Выходные данные
3
1 6
2 3
6 1