You are given a circular array A containing N integers. You can perform the following operation on this array any number of items:

• For each i, replace A[i] by A[i-1], A[i] or A[i+1] i.e. you can keep the current element or replace it by an adjacent element . Note that due to circularity of the array adjacent elements exist even for the first and the last element. In particular, A[i-1] for i=0 is the last element.

Determine the minimum number of steps needed to make all the elements of the array equal.

Input Format The first line contains an integer, N, denoting the number of elements in A. Each line i of the N subsequent lines (where 0 $i< N) contains an integer describing A[i]. Constraints 1 <= N <= 10^3

Sample input: 4 2 2 1 1 => Sample output: 1

Sample input:3 1 1 1 => Sample output: 0

Sample input:4 1 2 3 4 => Sample output: 2