Sử dụng cấp phát động, nhập ~n~ giá trị nguyên của mảng A, thực hiện chèn số 0 vào trước các phần tử chẵn của nó và in mảng mới ra.

Input

Dòng đầu tiên gồm số ~n~ cho biết kích thước mảng với ~1 \le n \le 100.~

Dòng tiếp theo gồm giá trị các phần tử của mảng A, các số tự nhiên không vượt ~2023.~

Output

Dòng đầu tiên cho biết kích thước của mảng mới.

Dòng tiếp theo là giá trị các phần tử của mảng mới.

Sample input

5
1 2 3 4 5

Sample output

7
1 0 2 3 0 4 5