Một dãy số được gọi là dãy số đặc biệt khi ta đọc dãy từ trái sang phải cũng giống như khi đọc từ phải sang trái.

Chẳng hạn:

• Dãy gồm các số \((21, 1, 9, 1, 21)\) là dãy số đặc biệt.
• Dãy gồm các số \((1, 7, 8, 9, 1)\) không phải là dãy số đặc biệt.

Yêu cầu: Cho số nguyên dương \(N\) và dãy số \(A\) gồm \(N\) phần tử \(a_1, a_2, \ldots, a_n\), mỗi phần tử là một số nguyên dương. Hãy tìm số lượng ít nhất phần tử cần chèn thêm vào dãy \(A\) để dãy \(A\) thành dãy số đặc biệt.

Input

• Dòng đầu là số tự nhiên \(N \leq 1000\);
• Dòng thứ 2 gồm \(N\) số nguyên dương \(a_1, a_2, a_3, \ldots, a_n\) \((0 \leq a_i \leq 10^9)\).

Output

• Ghi kết quả tìm được ra màn hình.
• Các số trên một dòng của tập input/output phải cách nhau ít nhất một dấu cách.

Example

5
1 7 8 9 1

2