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;
using Int = int_fast64_t;

Int n, ans = 1e9;
vector<Int> a(1, 0);
vector<Int> b(24);

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for(Int i=0; i<n; ++i){
		Int t; cin >> t;
		a.push_back(t);
	}
	sort(a.begin(), a.end());
	for(size_t i=0; i<a.size(); ++i){
		if(i % 2 == 0){
			if(b[a[i]] > 0){
				cout << 0 << "\n";
				return 0;
			}else{
				++b[a[i]];
			}
		}else{
			if(b[(24-a[i])%24] > 0){
				cout << 0 << "\n";
				return 0;
			}else{
				++b[24-a[i]];
			}
		}
	}
//	for(Int i=0; i<24; ++i) cout << i << " " << b[i] << "\n";
	for(Int i=0; i<23; ++i)
		for(Int j=i+1; j<24; ++j)
			if(b[i] & b[j])
				ans = min({ans, j-i, 24-j});
	cout << ans << "\n";
}