Tèo rất thích các bài toán về dãy số, sau một thời gian nghiên cứu về quy luật của dãy số Tèo cảm thấy không còn thú vị vì cậu ta đã biết được hầu hết các quy luật của dãy số. Bây giờ Tèo chuyển qua nghiên cứu về việc biến đổi dãy số.

Yêu cầu: Cho trước một dãy gồm nhiều số mà trong dãy chỉ chứa số ~1~ hoặc số ~2~, Tèo phải thực hiện ít nhất bao nhiêu thao tác biến đổi số ~1~ thành số ~2~ hoặc số ~2~ thành số ~1~ để thu được một dãy số mới không giảm. Ví dụ dãy số ban đầu là: ~2, 1, 2, 2, 1~. Tèo cần ít nhất ~2~ lần biến đổi để thành dãy: ~1, 1, 2, 2, 2~.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ n ~.
• Dòng thứ hai ghi ~ n ~ số nguyên thuộc ~ {1, 2} ~. Giữa các số được ghi cách nhau một dấu cách.

Kết quả

• Ghi một số nguyên duy nhất là số phép biến đổi ít nhất Tèo cần thực hiện.

Ràng buộc

• Có 50% số test với ~ 1 ≤ n ≤ 2000 ~.
• Có 50% số test với ~ 1 ≤ n ≤ 10^6 ~.

Ví dụ:

Input 1

5
2 1 2 2 1 

Output 1

2