Petya 和 Gena 喜欢打乒乓球。单场比赛按照以下规则进行:一场比赛由多盘组成,每盘由多个发球组成。每发球由一名球员获胜,该球员得一分。一旦其中一名选手获得 t 分,他就赢得这一盘;然后下一盘开始,双方得分均设为 0。只要其中一方赢得 s 盘总分,他就赢得比赛,比赛结束。这里 s 和 t 是一些正整数。
为了增加趣味性,Petya 和 Gena 在每场比赛前都会选择新的号码 s 和 t。此外,为了历史的缘故,他们保留每场比赛的记录:也就是说,他们为每次发球写下获胜者。发球获胜者按时间顺序记录。在一项记录中,只要其中一名球员得到 t 分,该盘就结束,而一旦其中一名球员赢得 s 盘,比赛就结束。
Petya 和 Gena 找到了旧比赛的记录。不幸的是,记录中的发球顺序并未分为几组,并且给定比赛的号码 s 和 t 也丢失了。玩家现在想知道 s 和 t 的值可能是什么。你能确定所有可能的选项吗?
输入
第一行包含一个整数 n — 游戏序列的长度 (1 ≤ n ≤ 105)。
第二行包含 n 个空格分隔的整数 ai。如果ai=1,那么第i个发球由Petya赢得,如果ai=2,那么第i个发球由Gena赢得。
不保证数字 s 和 t 的至少一个选项对应于给定记录。
输出
在第一行中打印一个数字 k — 数字 s 和 t 的选项数量。
在接下来的 k 行中,每一行都打印两个整数 si 和 ti - 数字 s 和 t 的选项。按照 si 递增的顺序打印选项,如果 si 相等,则按照 ti 递增的顺序打印选项。
示例
输入 #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