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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <numeric>
#include <iostream>

using namespace std;

#define FOR(i, a, b)   for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b)  for(int i = (a); i > (b); --i)
#define rep(i, n)      for(int i = 0; i < (n); ++i)
#define all(c)         begin(c), end(c)
#define rall(c)        rbegin(c), rend(c)
#define SZ(a)          ((ll) a.size())

typedef long long ll;
typedef unsigned long long ull;

int main(){
	int N;
	bool flag=false;
	scanf("%d",&N);
	vector<int> D(N+1);
	D[0]=0;
	rep(i,N) scanf("%d",&D[i+1]);
	sort(all(D));
	if(D[1]==0) flag=true;
	if(D[N]==12 and D[N-1] == 12) flag=true;
	rep(i,N-1){
		if(D[i]==D[i+1] and D[i+1]==D[i+2]) flag=true;
	}
	vector<int> E(D);
	int inv=0;
	int ans = -1;
	int tmp;
	if(flag) printf("0");
	else if(N>=12) printf("1");
	else{
		while(inv<pow(2,N)){
			rep(i,N){
				if((inv>>i)%2==1) {
					if(D[i+1]>0) E[i+1] = 24-D[i+1];
				}
				else{
					E[i+1] = D[i+1];
				}
			}
			tmp = 12;
			rep(i,N+1){
				FOR(j,i+1,N+1){
					tmp = min(tmp,min(abs(E[i]-E[j]),24-abs(E[i]-E[j])));
				}
			}
			ans = max(ans,tmp);
			inv+=1;
		}
		printf("%d",ans);
	}
  return 0;
}
