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.

Input

• 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}~, các số được ghi cách nhau một dấu cách.

Output

• Gồm 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.

Giới hạn

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

Example Test

Input

5
2 1 2 2 1

Output

2

Giải thích

• Với 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.