Bài tập

Một người nông dân có \(N\) luống rau, luống thứ \(i\) cho thu hoạch \(a_i\) gam. Ông muốn chọn một tập luống giao cho xe A và một tập luống khác giao cho xe B sao cho:

• Mỗi tập gồm ít nhất một luống, hai tập không có luống chung;
• Tổng lượng rau của hai xe bằng nhau.

Hãy đếm số cách chọn cặp \((\text{tập cho xe A}, \text{tập cho xe B})\). Cặp có thứ tự: đổi vai trò hai xe cho nhau được tính là một cách khác.

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• In ra số cách chọn.

Constraints

• \(1 \le N \le 22\)
• \(1 \le a_i \le 10^8\)

Sample Input 1

5
2 3 5 1 4

Sample Output 1

14

Sample Input 2

2
7 7

Sample Output 2

2

Explanation

Ở ví dụ 2 có hai cách: luống 1 cho xe A và luống 2 cho xe B, hoặc ngược lại.

Giai thừa của số nguyên dương \(N\), ký hiệu \(N!\), là tích \(1 \cdot 2 \cdot \ldots \cdot N\).

Cho \(m\) số nguyên dương \(N_1, N_2, \ldots, N_m\). Với mỗi số, hãy tính và in ra giai thừa của nó.

Gợi ý: viết hàm \(Fact(n)\) trả về \(n!\) và gọi nó cho từng số.

Input

• Dòng đầu tiên chứa số nguyên \(m\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên dương \(N_i\).

Output

• In ra \(m\) dòng, dòng thứ \(i\) là giá trị \(N_i!\).

Constraints

• \(1 \le m \le 10^5\)
• \(1 \le N_i \le 20\)

Sample Input 1

4
5
1
10
3

Sample Output 1

120
1
3628800
6

An có \(N\) chiếc đũa xanh với độ dài \(a_1, \dots, a_N\) và \(N\) chiếc đũa đỏ với độ dài \(b_1, \dots, b_N\).

An muốn ghép một đôi gồm đúng một đũa xanh và một đũa đỏ, sao cho hai chiếc có độ dài khác nhau. Hai đôi được coi là khác nhau nếu chúng khác nhau ở ít nhất một chiếc đũa (các chiếc đũa được phân biệt theo chỉ số, kể cả khi cùng độ dài).

Hãy đếm số đôi đũa hợp lệ.

Input

• Dòng đầu chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(a_1, \dots, a_N\).
• Dòng thứ ba chứa \(b_1, \dots, b_N\).

Output

In ra một số nguyên là số đôi đũa hợp lệ.

Constraints

• \(1 \le N \le 200\,000\).
• \(1 \le a_i, b_i \le 10^9\).

Sample Input

5
4 1 4 2 7
4 4 2 7 7

Sample Output

18

Explanation

Tổng cộng có \(25\) cặp; các cặp cùng độ dài: độ dài \(4\) có \(2 \cdot 2 = 4\) cặp, độ dài \(2\) có \(1\) cặp, độ dài \(7\) có \(1 \cdot 2 = 2\) cặp, tổng \(7\) cặp. Đáp số \(25 - 7 = 18\).

Trên một xa lộ thẳng có \(N\) thị trấn đánh số từ \(1\) đến \(N\); thị trấn \(i\) cách điểm đầu đường \(d_i\) đơn vị (các giá trị \(d_i\) không nhất thiết đôi một khác nhau hay đã sắp xếp).

Có \(Q\) cặp bạn, mỗi cặp là hai người ở thị trấn \(x\) và \(y\). Họ muốn chọn một thị trấn \(z\) (có thể trùng với \(x\) hoặc \(y\)) làm nơi hẹn sao cho người phải đi xa hơn đi càng ít càng tốt, tức là giá trị

là nhỏ nhất. Với mỗi cặp, hãy in ra giá trị nhỏ nhất này.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên \(d_1, \dots, d_N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\).

Output

In \(Q\) dòng, dòng thứ \(j\) là đáp án của cặp thứ \(j\).

Constraints

• \(1 \le N, Q \le 10^5\)
• \(1 \le d_i \le 10^9\)
• \(1 \le x, y \le N\)

Sample Input

6 3
2 9 4 15 7 11
1 4
3 3
2 5

Sample Output

7
0
2

Explanation

Cặp \((1, 4)\) ở vị trí \(2\) và \(15\): chọn \(z = 2\) (vị trí \(9\)) cho giá trị \(\max(7, 6) = 7\); chọn thị trấn \(5\) (vị trí \(7\)) cho \(\max(5, 8) = 8\). Đáp án là \(7\).