Description

聪聪和笨笨经常一起打乒乓球，为了增加趣味，他们自己制定的获胜规则有些不同，具体地说，他们两人在每局中先获得t分的人会赢得本局的胜利，而先赢得s局的人将成为胜者。
上个月的某一天，他们一共进行了n分的较量决出了比赛的胜者，并且按顺序记录下了每分的获得者，但是现在他们却记不起来当时的s与t是多少，现在请你帮助他们求出所有符合当时得分记录的(s,t)。
这里要提醒大家注意，只要某个人在一局中得到了t分，本局就会结束，双方选手得分清零，并开始下一局比赛；而当某人赢得了s局，本次比赛就会结束，之后不会再有交手。

Format

Input

第一行一个整数n表示得分数量。
接下来一行n个整数，每个数是1或2,1表示聪聪赢得这一分，2表示笨笨赢得这一分。

Output

第一行一个整数m，表示符合条件的(s,t)的数量。
接下来m行每行两个整数符合条件的一组(s,t)。
所有的(s,t)按照递增顺序输出，若s相等按照t递增顺序输出。

Sample 1

Input

4
1 2 1 2

Output

0

Sample 2

Input

4
1 1 1 1

Output

3
1 4
2 2
4 1

Sample 3

Input

5
1 2 1 2 1

Output

2
1 3
3 1

Sample 4

Input

8
2 1 2 1 1 1 1 1

Output

3
1 6
2 3
6 1

Limitation

【数据规模】
30%的数据：n <= 10
60%的数据：n <= 1000
100%的数据：1 <= n <= 10^5