Trận đấu bóng bàn

Petya và Gena chơi bóng bàn với nhau. Một trận đấu diễn ra theo luật sau: trận đấu gồm nhiều ván, mỗi ván gồm nhiều pha giao bóng. Mỗi pha giao bóng do đúng một người thắng và người đó được $1$ điểm. Ngay khi một người đạt $t$ điểm, người đó thắng ván hiện tại, ván mới bắt đầu và điểm của cả hai được đặt lại về $0$. Ngay khi một người thắng tổng cộng $s$ ván, người đó thắng cả trận và trận đấu kết thúc. Ở đây $s$ và $t$ là hai số nguyên dương.

Trước mỗi trận, hai người tự chọn ra cặp số $s$ và $t$ mới. Họ cũng ghi lại biên bản của trận: với mỗi pha giao bóng, họ ghi lại ai là người thắng pha đó, theo đúng thứ tự thời gian.

Nay họ tìm được biên bản của một trận đấu cũ, nhưng biên bản chỉ là dãy người thắng từng pha giao bóng, không đánh dấu ranh giới giữa các ván, và cặp số $s$, $t$ của trận đó cũng đã thất lạc. Hãy tìm tất cả các cặp $(s,t)$ có thể.

Một cặp $(s,t)$ là hợp lệ nếu khi chia biên bản theo luật trên thì:

• Ván cuối cùng kết thúc đúng tại pha giao bóng cuối cùng của biên bản (không dư pha nào, và không có ván nào dang dở).
• Người thắng ván cuối cùng chính là người thắng cả trận, tức là người đó thắng đúng $s$ ván và nhiều ván hơn đối thủ.

Lưu ý rằng có thể không tồn tại cặp $(s,t)$ nào phù hợp với biên bản đã cho.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$: độ dài biên bản (số pha giao bóng).
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$. Nếu $a_i=1$ thì pha giao bóng thứ $i$ do Petya thắng, nếu $a_i=2$ thì do Gena thắng.

Dữ liệu ra

• Dòng đầu in ra số nguyên $k$: số cặp $(s,t)$ hợp lệ.
• $k$ dòng tiếp theo, mỗi dòng in hai số nguyên $s_i$ và $t_i$. In các cặp theo thứ tự $s_i$ tăng dần, các cặp có cùng $s_i$ thì theo $t_i$ tăng dần.

Ràng buộc

• $1\le n\le {10}^5$
• $a_i\in \{1,2\}$

Ví dụ