Bài tập

Cho dãy số nguyên không âm \(A_1, A_2, \ldots, A_n\). Một cặp chỉ số \((i, j)\) được gọi là cặp gấp năm nếu thỏa mãn đồng thời:

• \(i < j\);
• \(A_i = 5 \cdot A_j\).

Hãy đếm số cặp gấp năm trong dãy.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \ldots, A_n\).

Output

• In ra một số nguyên duy nhất là số cặp gấp năm.

Constraints

• Subtask 1 (60% số điểm): \(n \le 10^3\), \(0 \le A_i \le 10^9\).
• Subtask 2 (40% số điểm): \(n \le 3 \cdot 10^5\), \(0 \le A_i \le 10^{18}\).

Sample Input 1

6
10 2 50 2 10 10

Sample Output 1

4

Explanation

Các cặp thỏa mãn: \((1,2)\), \((1,4)\) (cùng có \(10 = 5 \cdot 2\)) và \((3,5)\), \((3,6)\) (cùng có \(50 = 5 \cdot 10\)).

Một xã miền núi có \(N\) thôn, thôn thứ \(i\) nằm ở độ cao \(h_i\) mét so với mực nước biển. Người ta cần chọn đúng \(k\) thôn để lắp hệ thống bơm nước chung, sao cho hiệu giữa độ cao lớn nhất và độ cao nhỏ nhất trong \(k\) thôn được chọn là bé nhất có thể.

Hãy tính giá trị nhỏ nhất đó.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(k\).
• Dòng thứ hai chứa \(N\) số nguyên \(h_1, h_2, \dots, h_N\).

Output

In ra một số nguyên là hiệu độ cao nhỏ nhất có thể đạt được.

Constraints

• \(1 \le k \le N \le 10^5\)
• \(1 \le h_i \le 10^9\)

Sample Input

7 3
10 4 20 12 5 30 11

Sample Output

2

Explanation

Chọn các thôn có độ cao \(10, 11, 12\): hiệu là \(12 - 10 = 2\), không có cách chọn nào tốt hơn.

Cho hai số nguyên dương \(a\) và \(b\) với \(a \le b\). Hãy đếm xem trong đoạn \([a, b]\) (tính cả hai đầu mút) có bao nhiêu số nguyên chẵn đồng thời chia hết cho \(3\).

Input

• Một dòng chứa hai số nguyên dương \(a, b\).

Output

• In ra số lượng các số thỏa mãn.

Constraints

• \(1 \le a \le b \le 10^{10}\)

Sample Input 1

10 100

Sample Output 1

15

Explanation

Các số cần tìm là các bội của \(6\) trong đoạn \([10, 100]\): \(12, 18, \ldots, 96\), tổng cộng \(15\) số.

Cho hai số nguyên dương \(a\) và \(b\). Hãy tìm số nguyên dương nhỏ nhất chia hết cho cả \(a\) lẫn \(b\).

Input

Một dòng gồm hai số nguyên \(a\) và \(b\).

Output

In ra bội chung nhỏ nhất của \(a\) và \(b\).

Constraints

• \(1 \le a, b \le 10^{18}\)
• Đảm bảo kết quả không vượt quá \(10^{18}\).

Sample Input 1

4 6

Sample Output 1

12

Sample Input 2

9 3

Sample Output 2

9