Cho $2n$ số nguyên phân biệt $a_1$,$a_2$,…,$a_{2n}$. Một cách xếp $2n$ số thành $n$ nhóm gọi là cách xếp GRN nếu chênh lệch giữa hai số trong cùng một nhóm bằng với chênh lệch giữa hai số trong cùng nhóm khác. Hai cách xếp GRN được gọi là khác nhau nếu tồn tại hai số trong cách xếp này thì cùng nhóm nhưng trong cách xếp kia thì khác nhóm.

Yêu cầu: Cho $2n$ số nguyên phân biệt $a_1$,$a_2$,…,$a_{2n}$, hãy đếm số cách xếp GRN.

Dữ liệu vao:

• Dòng đầu là số nguyên dương $n$;
• Dòng thứ hai gồm $2n$ số nguyên, các số đôi một khác nhau và có giá trị tuyệt đối không vượt quá ${10}^9$.

Kết quả: Ghi ra một số là số cách xếp GRN.

Vi du:

Input

2
1 3 7 5

Output

2

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài có $n$ = 2;
• Có 20% test khác ứng với 20% số điểm của bài có $n$ ≤ 5;
• Có 20% test khác ứng với 20% số điểm của bài có $n$ ≤ 100;
• Có 20% test khác ứng với 20% số điểm của bài có $n$ ≤ 1000;
• Có 20% số test còn lại ứng với 20% số điểm của bài có $n$ ≤ ${10}^6$ và $a_i$ = $a_{i-1}$ + 1 ($1<i\le 2n$)</li>