Một dãy số được gọi là đặc biệt khi đọc từ trái sang phải cũng giống như đọc từ phải sang trái. Ví dụ: Dãy số \({21, 9 , 12, 9, 21}\) là dãy số đặc biệt.

Yêu cầu: Cho số nguyên dương \(N\) và dãy số nguyên dương \(a_1,a_2,.,,,a_N\).

Hãy tìm ít nhất các phần tử cần chèn thêm vào để dãy \(a\) tạo thành dãy số đặc biệt.

Input

• Dòng 1 chứa số nguyên \(N(1≤N≤10^3 ).\)

• Dòng thứ 2 chứa \(N\) số nguyên dương \(a_1,a_2,…,a_N (1≤a_i≤10^9 ).\)

Output

• Ghi một số nguyên dương là số lượng phần tử ít nhất chèn thêm vào để dãy \(a\) là dãy số đặc biệt

Sample Input

5
1 7 8 9 1

Sample Output

2