In CODE FESTIVAL XXXX, there are N+1 participants from all over the world, including Takahashi.

Takahashi checked and found that the time gap (defined below) between the local times in his city and the i-th person's city was D_i hours. The time gap between two cities is defined as follows. For two cities A and B, if the local time in city B is d o'clock at the moment when the local time in city A is 0 o'clock, then the time gap between these two cities is defined to be min(d,24-d) hours. Here, we are using 24-hour notation. That is, the local time in the i-th person's city is either d o'clock or 24-d o'clock at the moment when the local time in Takahashi's city is 0 o'clock, for example.

Then, for each pair of two people chosen from the N+1 people, he wrote out the time gap between their cities. Let the smallest time gap among them be s hours.

Find the maximum possible value of s.

Constraints

* 1 \leq N \leq 50
* 0 \leq D_i \leq 12
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
D_1 D_2 ... D_N


Output

Print the maximum possible value of s.

Examples

Input

3
7 12 8


Output

4


Input

2
11 11


Output

2


Input

1
0


Output

0
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;
const int MAX_N=50;
int N,D[MAX_N],V;
vector<int> G[MAX_N*2],rG[MAX_N*2];
bool used[MAX_N*2];
int scccmp[MAX_N*2];
vector<int> vs;
void add_edge(int s,int t){
	G[s].push_back(t);
	rG[t].push_back(s);
}
void dfs(int v){
	used[v]=true;
	for(auto e:G[v]){
		if(!used[e]){
			dfs(e);
		}
	}
	vs.push_back(v);
}
void dfs2(int v,int k){
	used[v]=true;
	scccmp[v]=k;
	for(auto e:rG[v]){
		if(!used[e]){
			dfs2(e,k);
		}
	}
}
void scc(){
	int V=N*2;
	memset(used,false,sizeof(used));
	vs.clear();
	REP(i,V){
		if(!used[i]){
			dfs(i);
		}
	}
	reverse(vs.begin(),vs.end());
	memset(used,false,sizeof(used));
	int k=0;
	for(auto v:vs){
		if(!used[v]){
			dfs2(v,k);
			k++;
		}
	}
}
int tmdif(int t1,int t2){
	int d=abs(t1-t2);
	return min(d,24-d);
}
bool C(int x){
	REP(i,N){
		REP(j,N){
			if(i==j)continue;
			REP(a,2)REP(b,2){
				int t1=(a==0 ? D[i] : 24-D[i]),t2=(b==0 ? D[j] : 24-D[j]);
				if(tmdif(t1,t2)<x){
					add_edge(i+a*N,j+(1-b)*N);
					add_edge(j+b*N,i+(1-a)*N);
				}
			}
		}
	}
	scc();
	REP(i,N){
		if(scccmp[i]==scccmp[i+N]){
			return false;
		}
	}
	return true;
}
int main(){
	cin>>N;
	V=N*2;
	REP(i,N)cin>>D[i];
	int md=13;
	REP(i,N)md=min(md,D[i]);
	int ans=0;
	FOR(i,1,md+1){
		if(C(i)){
			ans=i;
		}
	}
	cout<<ans<<endl;
}