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
#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define REPN(i,n) for (int i=(n);i>=0;i--)
#define I(n) scanf("%d", &(n))
#define LL(n) scanf("%lld", &(n))
#define pb(n) push_back((n))
#define mp(i,j) make_pair((i),(j))
#include <bits/stdc++.h>
using namespace std;

int n,d[50],di[13],s,table,inittable;
int prevt,ret;

int solve(int table){
    prevt = 0;
    ret = 24;
    REP(i,24){
        if(table & 1){
            ret = min(ret, i - prevt);
            prevt = i;
        }
        table >>= 1;
    }
    return min(ret,24-prevt);
}

int main(){
    I(n);
    REP(i,n){ I(d[i]); di[d[i]]++; }
    if (di[0] || di[12] > 1 || *(max_element(di+1,di+12)) > 2){
        cout << 0 << endl;
        return 0;
    }
    inittable = di[12] ? 1 << 12 : 0;
    REP(bits,1<<12){
        table = inittable;
        REP(i,12){
            if (di[i] == 1){
                table |= 1 << ((bits >> i) & 1 ? i : 24 - i);
            } else if (di[i] == 2){
                table |= (1 << i) | (1 << (24 - i));
            }
        }
        s = max(s,solve(table));
    }
    cout << s << endl;
}
