Tennis Game

题意翻译

【题面描述】 $1$ 玩家和 $2$ 玩家打球。一场比赛分为好多局，每场比赛两人分数从 $0$ 记起，每赢一球就得一分。这一场比赛还有用来记录的序列。每一球如果 $1$ 玩家赢球，裁判就会写下 $1$，如果 $2$ 玩家赢球，裁判就会写下 $2$。 如果在一局中有人率先得到了 $t$ 分，他就赢下了这一局，这一局立马结束。如果在整场比赛中有人赢了 $s$ 局，他就赢下了这场比赛，比赛立马结束。 现在我们知道裁判记录下的序列，但不知道具体的 $s,t$，也不知道每一局比赛在序列上如何划分。现在就问你有多少种可能的 $s,t$，并输出。 【输入格式】 第一行一个整数 $n$，表示序列长度。（$1\leq n\leq10^5$） 第二行 $n$ 个整数，每个数是 $1$ 或 $2$，表示裁判记下的数列。 【输出格式】 第一行一个整数，表示合法的 $s,t$ 个数。 接下来若干行，输出 $s,t$ 方案。按照 $s$ 第一关键字，$t$ 第二关键字升序输出。 Translated by [kouylan](https://www.luogu.com.cn/user/123298).

题目描述

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?

输入输出格式

输入格式

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?

输出格式

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?

输入输出样例

输入样例 #1

5
1 2 1 2 1

输出样例 #1

2
1 3
3 1

输入样例 #2

4
1 1 1 1

输出样例 #2

3
1 4
2 2
4 1

输入样例 #3

4
1 2 1 2

输出样例 #3

0

输入样例 #4

8
2 1 2 1 1 1 1 1

输出样例 #4

3
1 6
2 3
6 1