Làm trơn trung vị

Cho dãy nhị phân $a_1,a_2,\dots ,a_n$ (mỗi phần tử bằng $0$ hoặc $1$). Phép làm trơn trung vị biến dãy $a$ thành dãy mới $b$ như sau:

• $b_1=a_1$ và $b_n=a_n$ (phần tử đầu và cuối giữ nguyên).
• Với $i=2,\dots ,n-1$: $b_i$ bằng trung vị của ba giá trị $a_{i-1},a_i,a_{i+1}$ (giá trị đứng giữa khi sắp xếp ba số theo thứ tự không giảm).

Một dãy gọi là ổn định nếu áp dụng phép làm trơn trung vị lên nó thì dãy không thay đổi.

Hãy xác định xem nếu áp dụng phép làm trơn trung vị lặp đi lặp lại lên dãy $a$ thì dãy có trở nên ổn định hay không. Nếu có, hãy in ra số lần áp dụng ít nhất để dãy trở nên ổn định và dãy ổn định thu được. Nếu dãy không bao giờ ổn định, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: độ dài dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($a_i\in \{0,1\}$).

Dữ liệu ra

• Nếu dãy không bao giờ ổn định, in ra một số duy nhất $-1$.
• Ngược lại, dòng đầu in số lần áp dụng ít nhất để dãy trở nên ổn định; dòng thứ hai in $n$ số của dãy ổn định thu được, cách nhau một dấu cách.

Ràng buộc

• $3\le n\le 500000$
• $a_i\in \{0,1\}$

Ví dụ