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"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 52;

int main(){
  int N,a[MAX_N];
  cin >> N;
  rep(i,N) cin >> a[i];
  if(N>=25){
    cout << "0" << endl;
    return 0;
  }
  int b[MAX_N];
  fill(b,b+13,0);
  if(N>=19&&N<=24){
    b[0]++;
    rep(i,N) b[a[i]]++;
    int _max = -INF;
    rep(i,13) _max = max(_max,b[i]);
    if(_max>=3||b[0]>=2) cout << "0" << endl;
    else cout << "1" << endl;
    return 0;
  }
  int ans = -INF;
  rep(i,1<<N){
    int ind = 0;
    b[ind++] = 0;
    rep(j,N){
      if(((1<<j)&i)!=0) b[ind++] = 24-a[j];
      else b[ind++] = a[j];
    }
    sort(b,b+N+1);
    int diff = 24 - b[N];
    rep(j,N) diff = min(diff,b[j+1]-b[j]);
    ans = max(ans,diff);
  }
  cout << ans << endl;
  return 0;
}