Bài tập

Trong một cuộc khảo sát môi trường, một nhóm các nhà sinh thái học đang nghiên cứu một hệ sinh thái tuyến tính, bao gồm \(n\) khu vực liên tiếp được đánh số từ \(1\) đến \(n\). Theo các nghiên cứu trước đó, có tổng cộng \(m\) loài sinh vật khác nhau được đánh số từ \(1\) tới \(m\). Các nhà khoa học đã ghi nhận mỗi khu vực \(i\) chỉ có một loài sinh vật đặc trưng là \(a_i\).

Để đánh giá sự đa dạng sinh học, các nhà khoa học đã chọn một đoạn khảo sát liên tiếp, từ khu vực \(l\) đến khu vực \(r\).

Một chỉ số được gọi là "chỉ số thiếu hụt đa dạng" được định nghĩa cho mỗi đoạn khảo sát \((l, r)\) như sau:

• Giả sử sau khi thống kê các loài sinh vật từ khu vực \(l\) đến \(r\), có \(k\) loài chưa được ghi nhận, lần lượt là \(c_1, c_2, \ldots, c_k\).
• "Chỉ số thiếu hụt đa dạng" sẽ bằng với tổng của các chỉ số loài này: \(c_1 + c_2 + \ldots + c_k\).

Để đưa ra báo cáo tổng quan về hệ sinh thái này, các nhà khoa học cần tính tổng "chỉ số thiếu hụt đa dạng" của tất cả các đoạn khảo sát liên tiếp \((x, y)\) với \(1 \le x \le y \le n\).

Yêu cầu: Cho trước \(n, m\) và mảng \(a\). Hãy tính tổng "chỉ số thiếu hụt đa dạng" của tất cả các đoạn khảo sát liên tiếp.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 2 \times 10^5, 1 \le m \le 10^9\)) lần lượt là số khu vực và số loại sinh vật.
• Dòng thứ hai chứa \(n\) số \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le m\)) là loại sinh vật đặc trưng ở mỗi khu vực.
• Lưu ý rằng có thể có các khu vực khác nhau cùng có một loại sinh vật, hoặc có loại không có khu vực nào.

Output

• In ra tổng "chỉ số thiếu hụt đa dạng" của mọi đoạn. Vì kết quả có thể rất lớn, hãy in ra sau khi chia lấy dư cho \(998244353\).

Example

3 4
1 2 3

40

8 4
2 3 1 2 4 3 1 3

124

Scoring

• Subtask 1 (20% số điểm): \(1 \le n, m \le 50\).
• Subtask 2 (20% số điểm): \(1 \le n, m \le 500\).
• Subtask 3 (20% số điểm): \(1 \le n, m \le 5000\).
• Subtask 4 (20% số điểm): \(m = 2\).
• Subtask 5 (20% số điểm): không có ràng buộc gì thêm.

Linh là một học sinh rất yêu thích lập trình. Gần đây, Linh đang phát triển một robot có thể phân tích chuỗi số và tìm các đoạn "dễ thương".

Cụ thể, một đoạn con liên tiếp \((l, r)\) của dãy \(A_1, A_2, \ldots, A_n\) được gọi là dễ thương nếu:

• \(max - min = k\), với \(max\) là giá trị lớn nhất và \(min\) là giá trị nhỏ nhất trong đoạn đó.

Linh muốn bạn giúp đếm xem trong dãy ban đầu có tất cả bao nhiêu đoạn con dễ thương.

\InputFile

• Dòng đầu tiên gồm hai số nguyên \(n, k\) (\(1 \le n \le 5 \times 10^5\), \(0 \le k \le 10^9\)).
• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(-10^9 \le A_i \le 10^9\)).

\OutputFile

In ra một số nguyên duy nhất --- số lượng đoạn con dễ thương trong dãy.

\Scoring

• Subtask 1 (40% số điểm): \(n \le 10^3\).
• Subtask 2 (30% số điểm): \(n \le 10^5\).
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.

Example

5 2
1 2 1 3 3

6

An rất yêu thích tuyết. Trong \(n\) ngày, mỗi ngày Bình tạo ra một đống tuyết có thể tích \(v_i\).
Nhưng mỗi ngày, nhiệt độ \(t_i\) khiến mỗi đống tuyết (kể cả đống mới tạo) bị giảm đúng \(t_i\) đơn vị.
Đống tuyết nào giảm xuống \(\le 0\) thì biến mất.

Nhiệm vụ của bạn: Tính tổng thể tích tuyết bị tan chảy trong mỗi ngày.

Input

• Dòng 1: số nguyên \(n\) (\(1 \le n \le 10^5\)).
• Dòng 2: \(v_1, v_2, \dots, v_n\) (\(0 \le v_i \le 10^9\)).
• Dòng 3: \(t_1, t_2, \dots, t_n\) (\(0 \le t_i \le 10^9\)).

Output

Một dòng gồm \(n\) số --- lượng tuyết tan trong từng ngày.

Example

3
10 10 5
5 7 2

5 12 4

Scoring

• Subtask 1 (10%): \(t_i = 0\).
• Subtask 2 (30%): \(n, t_i, v_i \le 10^3\).
• Subtask 3 (60%): Không có ràng buộc thêm.

Vua của vương quốc Algorithmia muốn quy hoạch một khu vườn hình chữ nhật trong khuôn viên hoàng cung. Khu đất dự kiến được chia thành lưới ô vuông kích thước \(n \times m\). Mỗi ô \((i, j)\) có độ phì nhiêu của đất là \(a_{i,j}\).

Nhà vua muốn rào một khu đất hình chữ nhật con (có các cạnh song song với các cạnh của khu đất lớn) để trồng một loài hoa quý. Loài hoa này rất kén chọn, nó chỉ phát triển tốt nếu tổng độ phì nhiêu của toàn bộ khu đất hình chữ nhật đó nằm trong khoảng từ \(L\) đến \(R\).

Nhiệm vụ của bạn là đếm xem có bao nhiêu cách chọn một hình chữ nhật con thỏa mãn yêu cầu của nhà vua.

Input

Vào từ tệp văn bản KHUVUON.INP có cấu trúc:

• Dòng đầu tiên chứa bốn số nguyên \(n, m, L, R\) (\(1 \le n, m \le 500, 1 \le L \le R \le 10^{12}\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên dương biểu diễn ma trận độ phì nhiêu \(a\) (\(1 \le a_{i,j} \le 10^9\)).

Output

Ghi ra tệp văn bản KHUVUON.OUT một số nguyên duy nhất là số lượng hình chữ nhật con thỏa mãn.

Example

3 3 3 5
1 1 1
1 1 1
1 1 1

10

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n, m \le 10\).
• Subtask 2 (\(30\%\) số điểm): \(n, m \le 100\).
• Subtask 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.