ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5394: 网球游戏

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：5 通过：5
提交提交记录统计Web Board

题目描述

Petya和Gena喜欢打乒乓球。单打比赛的规则如下:一场比赛由多盘组成，每盘由多次发球组成。每一次发球都由其中一名选手获胜，该选手得一分。只要其中一名选手得到 t 分，他就赢得了这盘比赛;然后下一盘开始，双方的分数都被重设为0。一旦其中一名选手总共赢得了 s 局，他就赢得了比赛，比赛就结束了。这里 s 和 t 是正整数。

为了增加乐趣，Petya和Gena在每场比赛前都会选择新的数字 s 和 t 。此外，为了回溯过往成绩，他们对每一场比赛都有记录:也就是说，每发一次球，他们都记下获胜者。发球冠军按时间顺序记录。在记录中，当其中一名选手得分 t 分时，一局比赛结束;当其中一名选手赢得 s 局时，整场比赛结束。

彼佳和吉纳找到了一份旧比赛记录。不幸的是，记录中的发球顺序没有被划分为几局，给定比赛的数字s和t也会丢失。玩家现在想知道 s 和 t 的值是多少。

你能确定所有可能的选择吗?



Petya and Gena love playing table tennis. A single match is played according to the following rules: a match consists of multiple sets, each set consists of multiple serves. Each serve is won by one of the players, this player scores one point. As soon as one of the players scores t points, he wins the set; then the next set starts and scores of both players are being set to 0. As soon as one of the players wins the total of s sets, he wins the match and the match is over. Here s and t are some positive integer numbers.
To spice it up, Petya and Gena choose new numbers s and t before every match. Besides, for the sake of history they keep a record of each match: that is, for each serve they write down the winner. Serve winners are recorded in the chronological order. In a record the set is over as soon as one of the players scores t points and the match is over as soon as one of the players wins s sets.
Petya and Gena have found a record of an old match. Unfortunately, the sequence of serves in the record isn't divided into sets and numbers s and t for the given match are also lost. The players now wonder what values of s and t might be. Can you determine all the possible options?
Input
The first line contains a single integer n− the length of the sequence of games (1≤n≤105).
The second line contains n space-separated integers ai. If ai=1, then the i-th serve was won by Petya, if ai=2, then the i-th serve was won by Gena.
It is not guaranteed that at least one option for numbers s and t corresponds to the given record.
Output
In the first line print a single number k− the number of options for numbers s and t.
In each of the following k lines print two integers si and ti− the option for numbers s and t. Print the options in the order of increasing si, and for equal si− in the order of increasing ti.
Examples
Input 
5
1 2 1 2 1
Output 
2
1 3
3 1
Input 
4
1 1 1 1
Output 
3
1 4
2 2
4 1
Input 
4
1 2 1 2
Output 
0
Input 
8
2 1 2 1 1 1 1 1
Output 
3
1 6
2 3
6 1

输入格式

第一行包含一个整数n，即比赛记录的长度(1≤n≤105)。

第二行包含n个以空格分隔的整数ai。如果ai=1，那么第i次发球是Petya赢，如果ai=2，那么第i次发球是Gena赢。

不能保证数字 s 和 t 的至少一个选项对应于给定的记录。

输出格式

在第一行打印单个数字 k，即 s 和 t 的数量。

在下面的k行中，每一行打印两个整数 si 和 ti 。按照 si 的递增顺序输出答案，对于相等的 si ，则按照 ti 的递增顺序输出。

输入样例 复制 

5
1 2 1 2 1

输出样例 复制 

2
1 3
3 1

数据范围与提示

样例一中，第1次发球Petya赢，第2次发球是Gena赢，第3次Petya赢，第4次Gena赢，第5次Petya赢的情况，可能的选项有2种，一种是赢1局即可，一局赢3个球；另一种情况是赢3局，一局赢1球即可。

分类标签