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>

using namespace std;
#define BUF (1000)
#define ll long long 

int n;
int D[BUF];
int dcnt[13];
int used[25];
int ans;


void dfs(int d){
	int sm,bg;
	sm=D[d];
	bg=24-D[d];

	if(d==n+1){
		//count used!!!!
		int cnt=0;
		int index=0;
		int min = 1000;
		for(int i=0;i<=24;i++){
			
			if(used[i]==1){
				cnt=i-index;
				index = i;
				if(min>cnt) min = cnt;
			}
		}

//		cout << min << "calc\n";
		if(min==1000) return ;
		if(min>ans) ans = min;
		return;
	}

	if(used[sm]==0){

		used[sm]=1;

//		cout << d << sm << "\n";	
		dfs(d+1);
		used[sm]=0;
	}

	if(used[bg]==0){

//		cout << d << bg << "\n";	
		used[bg]=1;
		dfs(d+1);
		used[bg]=0;
	}

	if(used[bg]==1 && used[sm]==1) return;
}

int main(void){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> D[i];
		dcnt[D[i]]++;
	}

	for(int i=1;i<12;i++){
		if(dcnt[i]>2){ 
			cout << 0;
			return 0;
		}
	}

	if(dcnt[0]>0){
		cout << 0;
		return 0;
	}

	if(dcnt[12]>1){
		cout << 0;
		return 0;
	}

	if(n==1){
		int sm=D[1];
		int bg=24-sm;
		cout << sm;
		return 0;
	}


/*
	for(int i=0;i<12;i++){
		if(dcnt[i]==2){ 
			used[i]=1;
			used[24-i]=1;
		}
	}
*/
	//used[0]=1;
	used[24]=1;
	dfs(1);

	cout << ans;
	return 0;
}
