Có \(n\) con bò, mã giống mỗi con là \(a_1, a_2,...a_n\)

0: bò thường
1: bò sữa
2: bò lai
3: bò tót

Các con bò rất hung hãn, nếu \(2\) con bò khác giống nhốt chung vào \(1\) chuồng thì chúng sẽ húc nhau

Yêu cầu: Sử dụng bao nhiêu chuồng bò, mỗi chuồng bao nhiêu con để chúng không xảy ra xung đột

Input

10
1    0   -1   2   7   7   2   7   -1   2

output

-1 2
0 1
1 1
2 3
7 3

\(40%\) số test \(n<=100\)
\(30%\) số test \(n <=10^5\) và \(|a_i| <=10^6\)
\(30%\) số test \(n<=10^5\) và \(|a_i| <=10^9\)