Trong một buổi trình diễn ánh sáng nghệ thuật, hệ thống điều khiển phát ra một dãy hiệu lệnh dài ~n~. Mỗi hiệu lệnh là một ký tự trong chuỗi ~s~:

• ~R~ — tăng mức đỏ lên ~1~.
• ~B~ — tăng mức xanh lên ~1~.
• ~N~ — không thay đổi mức màu.

Một đoạn liên tiếp ~s[l..r]~ (với ~1 \le l \le r \le n~) được gọi là cân bằng màu nếu sau khi thực hiện toàn bộ các hiệu lệnh trong đoạn đó, tổng mức tăng đỏ bằng tổng mức tăng xanh, tức là trong đoạn có số lượng ~R~ bằng số lượng ~B~ (các ký tự ~N~ không ảnh hưởng).

Yêu cầu

Hãy tính số lượng đoạn liên tiếp của chuỗi ~s~ sao cho đoạn đó là cân bằng màu.

Dữ liệu

• Dòng ~1~: số nguyên dương ~n~ — độ dài chuỗi.
• Dòng ~2~: chuỗi ~s~ độ dài ~n~, chỉ gồm các ký tự ~R~, ~B~, ~N~.

Kết quả

• In ra một số nguyên — số đoạn liên tiếp cân bằng màu.

Ví dụ

Ví dụ 1

Input

8
RBNRBNRN

Output

16

Ràng buộc và chấm điểm

Thành phố Ánh Sáng đánh số các cột đèn bằng các số nguyên dương tăng dần. Theo thiết kế:

• Cột đèn có mã số là số nguyên tố được lắp bộ điều khiển thông minh (gọi là đèn thông minh).
• Các cột còn lại là đèn thường.

Do quy mô lớn, mã số có thể rất lớn (tới hàng tỷ). Bạn cần trả lời nhiều truy vấn hỏi số lượng đèn thông minh trong một đoạn.

Yêu cầu

Với mỗi truy vấn ~L, R~, hãy xác định có bao nhiêu số nguyên tố nằm trong đoạn ~[L, R]~.

Dữ liệu

• Dòng ~1~: số nguyên ~T~ — số lượng truy vấn.
• ~T~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~L, R~.

Kết quả

• Với mỗi truy vấn, in ra một dòng — số lượng số nguyên tố trong đoạn ~[L, R]~.

Ví dụ

Ví dụ 1

Input

3
1 10
10 20
100 120

Output

4
4
5

Giải thích

Ví dụ 1

• Đoạn ~[1,10]~ có các số nguyên tố: ~2,3,5,7~ nên kết quả là ~4~.
• Đoạn ~[10,20]~ có các số nguyên tố: ~11,13,17,19~ nên kết quả là ~4~.
• Đoạn ~[100,120]~ có các số nguyên tố: ~101,103,107,109,113~ nên kết quả là ~5~.

Ràng buộc và chấm điểm

Ngoài ra luôn có: ~1 \le L \le R \le 2 \times 10^9~, và ~R - L \le 10^6~.

Trong ngày hội Xuân, có ~N~ hộp quà được đánh số từ ~1~ đến ~N~. Hộp quà thứ ~i~ có giá trị nguyên ~a_i~.

Người chiến thắng được chọn ba hộp quà sao cho độ chênh lệch giữa giá trị lớn nhất và nhỏ nhất trong ba hộp không vượt quá ~d~.

Ba hộp quà có chỉ số ~i < j < k~ được coi là hợp lệ nếu: ~\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k) \le d~.

Yêu cầu

Hãy đếm số bộ ba chỉ số ~ (i, j, k) ~ với ~1 \le i < j < k \le N~ thỏa mãn điều kiện trên.

Dữ liệu

• Dòng ~1~: hai số nguyên ~N~ và ~d~.
• Dòng ~2~: ~N~ số nguyên ~a_1, a_2, \dots, a_N~.

Kết quả

• In ra một số nguyên — số lượng bộ ba hợp lệ.

Ví dụ

Ví dụ 1

Input

5 3
6 1 7 2 4

Output

2

Giải thích

Ví dụ 1

Các bộ ba chỉ số hợp lệ là:

• ~(2, 4, 5)~ với các giá trị ~(1, 2, 4)~, có ~4 - 1 = 3 \le d~.
• ~(1, 3, 5)~ với các giá trị ~(6, 7, 4)~, có ~7 - 4 = 3 \le d~.

Vì vậy có tổng cộng ~2~ bộ ba hợp lệ.

Ràng buộc và chấm điểm

Ràng buộc

Ngoài ra: ~0 \le d \le 10^6~, ~1 \le a_i \le 10^6~.

Cho dãy số nguyên ~A = (a_1, a_2, \dots, a_n)~.

Một dãy số được gọi là cấp số cộng nếu hiệu giữa hai phần tử liên tiếp luôn bằng một hằng số (công sai). Dãy chỉ có một phần tử cũng được coi là cấp số cộng.

Ta gọi dãy con của ~A~ là dãy thu được bằng cách xóa đi một số (có thể là ~0~) phần tử của ~A~ và giữ nguyên thứ tự các phần tử còn lại.

Trong tất cả các dãy con của ~A~ mà là cấp số cộng (với công sai bất kỳ), hãy tìm độ dài lớn nhất có thể.

Yêu cầu

In ra độ dài lớn nhất của một dãy con của ~A~ sao cho dãy con đó là cấp số cộng.

Dữ liệu

• Dòng ~1~: số nguyên ~N~.
• Dòng ~2~: ~N~ số nguyên ~a_1, a_2, \dots, a_N~ (giá trị tuyệt đối không quá ~10^9~).

Kết quả

• Một dòng ghi một số nguyên — độ dài lớn nhất cần tìm.

Ví dụ

Ví dụ 1

Input

7
2 0 4 -1 6 -2 -3

Output

4

Ví dụ 2

Input

3
3 2 1

Output

3

Giải thích

Ví dụ 1

Một dãy con cấp số cộng dài nhất có thể là ~(2, 0, -2, -4)~ (chẳng hạn chọn các phần tử theo đúng thứ tự xuất hiện) với công sai ~-2~, nên đáp án là ~4~.

Ví dụ 2

Dãy ~(3, 2, 1)~ chính là một cấp số cộng với công sai ~-1~, nên độ dài lớn nhất là ~3~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 7000~.
• ~|a_i| \le 10^9~.

Chấm điểm