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<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<cmath>
    #include<ctime>
    #include<queue>
    #include<map>
    #include<set>
    #include<vector>
    #include<bitset>
    #include<cassert>
    #define rint register int
    #define debug(x) cerr<<#x<<"="<<x<<endl
    #define fgx cerr<<"-------------"<<endl
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    int d[100],a[100];
    int main()
    {	int n,maxn=0,mn=100; scanf("%d",&n);
    	if(n>=24){cout<<"0\n"; return 0;}
    	for(rint i=1;i<=n;i++) scanf("%d",&d[i]),mn=min(mn,d[i]);
    	if(mn==0){cout<<"0\n"; return 0;}
    	if(n==23){cout<<"1\n"; return 0;}
    	for(rint i=0;i<(1<<n);i++)
    	{	for(rint j=1;j<=n;j++) if(i&(1<<j-1)) a[j]=24-d[j]; else a[j]=d[j];
    		int minn=1000;
    		for(rint j=1;j<=n;j++)
    		{	for(rint k=1;k<j;k++)
    			{	int now=max(a[j]-a[k],a[k]-a[j]);
    				minn=min(minn,min(now,24-now));
    			}
    			minn=min(minn,min(a[j],24-a[j]));
    		}
    		maxn=max(maxn,minn);
    	}
    	cout<<maxn<<endl;
     	return 0;
    }