Cho mảng \(a\) gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) và số nguyên dương \(M\). Một đoạn con liên tiếp của mảng \(a\) là một dãy gồm các phần tử liên tiếp có dạng: \(a_i, a_{i+1}, ..., a_j\) (\(1 \le i \le j \le n\)), độ dài là \(j - i + 1\).

Trung vị của một đoạn con liên tiếp \(b\) có độ dài \(k\) được định nghĩa như sau:

1. Sắp xếp các phần tử của \(b\) theo thứ tự không giảm.
2. Khi đó:
   • Nếu \(k\) lẻ: Trung vị là phần tử ở vị trí \((k+1)/2\).
   • Nếu \(k\) chẵn: Trung vị là phần tử ở vị trí \(k/2\).

Yêu cầu: Hãy đếm số lượng đoạn con liên tiếp của mảng \(a\) có trung vị bằng \(M\).

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương \(n, M\) (\(1 \le M < n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) (\(a_i \le 10^6\); \(1 \le i \le n\)).

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc

• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: \(n \le 10^2\).
• Có 30% số test khác ứng với 30% số điểm của bài thỏa mãn: \(10^2 < n \le 5 \cdot 10^3\).
• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 2
2 1 3 4 5

Output

3

Giải thích
Các đoạn con liên tiếp có trung vị bằng \(2\) là:

• 2
• 2 1 3
• 2 1 3 4

Cho dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\) và ba số nguyên \(x, y, z\).

Yêu cầu: Tìm giá trị lớn nhất của biểu thức \(x \cdot a_i + y \cdot a_j + z \cdot a_k\) với (\(1 \le i < j < k \le n\)).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(3 \le n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(\vert{}a_i\vert{} \le 10^5\); \(1 \le i \le n\)).
• Dòng thứ ba chứa ba số nguyên \(x, y, z\) (\(\vert{}x\vert{}, \vert{}y\vert{}, \vert{}z\vert{} \le 10^5\)).

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là giá trị lớn nhất tìm được.

Ràng buộc

• Có 40% số test ứng với 40% số điểm của bài thỏa mãn: \(n \le 10^2\).
• Có 30% số test khác ứng với 30% số điểm của bài thỏa mãn: \(10^2 < n \le 10^6\); \(x = y = z\).
• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5
1 3 2 4 5
3 8 2

Output

51

Giải thích
Chọn ba số hạng \(a_2, a_4, a_5\).
Giá trị của biểu thức là: \(x \cdot a_2 + y \cdot a_4 + z \cdot a_5 = 3 \cdot 3 + 8 \cdot 4 + 2 \cdot 5 = 51\) (lớn nhất).

Số tự nhiên \(m\) được gọi là ước nguyên tố của số nguyên dương \(n\) nếu \(n\) chia hết cho \(m\) và \(m\) là số nguyên tố.
Ví dụ: Số \(12\) có \(2\) ước nguyên tố là \(2\) và \(3\); số \(30\) có \(3\) ước nguyên tố là \(2, 3\) và \(5\).

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn gồm ba số nguyên \(a, b, k\). Với mỗi truy vấn, hãy xác định số lượng các số nguyên \(x\) thỏa mãn: \(a \le x \le b\) và có số lượng ước nguyên tố không nhỏ hơn \(k\).

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương \(Q\) là số lượng truy vấn (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a, b, k\) (\(1 \le a \le b \le 10^6\); \(0 \le k \le 7\)).

Dữ liệu ra

• Gồm \(Q\) dòng, mỗi dòng ghi một số nguyên duy nhất là kết quả tương ứng với mỗi truy vấn.

Ràng buộc

• Có 60% số test ứng với 60% số điểm của bài thỏa mãn: \(Q = 1\); \(1 \le a \le b \le 10^3\).
• Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: \(Q = 1\); \(10^3 < a \le b \le 10^6\).
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

1
25 30 2

Output

3

Giải thích
Từ \(25\) đến \(30\) có \(3\) số có từ \(2\) ước nguyên tố trở lên đó là \(26, 28\) và \(30\). Cụ thể:

• \(26\) có \(2\) ước nguyên tố là \(2\) và \(13\).
• \(28\) có \(2\) ước nguyên tố là \(2\) và \(7\).
• \(30\) có \(3\) ước nguyên tố là \(2, 3\) và \(5\).

Cho số nguyên dương \(k\) (\(1 \le k \le 10^{12}\)).

Yêu cầu: Đếm số lượng các cặp số nguyên dương \(a, b\) thỏa mãn: \(a < b\) và \(a \cdot b \le k\).

Dữ liệu vào

• Gồm một dòng duy nhất chứa số nguyên \(k\).

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc

• Có 80% số test ứng với 80% số điểm của bài thỏa mãn: \(k \le 10^3\).
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

6

Output

6

Giải thích
Các cặp số thỏa mãn là: \((1,2)\), \((1,3)\), \((1,4)\), \((1,5)\), \((1,6)\), \((2,3)\).