🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Mùa nước nổi, thầy Sơn cùng bà con trong xóm ở Hồng Ngự gom lục bình về phơi khô để đan giỏ bán cho khách du lịch. Trước sân nhà thầy có ~N~ bó lục bình đã phơi, bó thứ ~i~ có đúng ~a_i~ sợi.

Để đan một chiếc giỏ, thầy Sơn chọn hai bó khác nhau ~i~ và ~j~ ~(i < j)~ rồi chia toàn bộ sợi của hai bó thành các lọn, sao cho:

• mỗi lọn chỉ gồm sợi lấy từ cùng một bó,
• mọi lọn có số sợi bằng nhau và không bó nào còn thừa sợi,
• mỗi lọn có số sợi nhiều nhất có thể.

Số sợi của mỗi lọn khi đó được gọi là độ dày của cặp bó ~(i, j)~. Ví dụ hai bó có ~6~ và ~9~ sợi thì mỗi lọn có ~3~ sợi (bó đầu thành ~2~ lọn, bó sau thành ~3~ lọn), độ dày là ~3~.

Mỗi đơn hàng của khách yêu cầu giỏ có độ dày nằm trong một khoảng cho trước. Thầy Sơn nhận ~Q~ đơn hàng, đơn thứ ~k~ cho hai số ~L_k, R_k~. Với mỗi đơn, hãy giúp thầy Sơn đếm xem có bao nhiêu cặp bó ~(i, j)~ với ~1 \le i < j \le N~ có độ dày nằm trong đoạn ~[L_k, R_k]~. Các đơn hàng độc lập với nhau (thầy chỉ đếm, không dùng hết lục bình).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N \le 3 \times 10^5,~ ~1 \le Q \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ ~(1 \le a_i \le 10^6)~.
• ~Q~ dòng tiếp theo, dòng thứ ~k~ chứa hai số nguyên ~L_k, R_k~ ~(1 \le L_k \le R_k \le 10^6)~.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~k~ là số cặp bó có độ dày thuộc đoạn ~[L_k, R_k]~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 2000~.
• Subtask 2 (~30\%~ số điểm): ~a_i \le 3000~ với mọi ~i~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

5 3
6 4 9 10 15
2 3
3 1000000
4 10

Sample Output 1

6
4
1

Giải thích

Có ~10~ cặp bó. Độ dày của từng cặp (ghi theo số sợi của hai bó):

• ~(6, 4) \to 2~; ~(6, 9) \to 3~; ~(6, 10) \to 2~; ~(6, 15) \to 3~;
• ~(4, 9) \to 1~; ~(4, 10) \to 2~; ~(4, 15) \to 1~;
• ~(9, 10) \to 1~; ~(9, 15) \to 3~;
• ~(10, 15) \to 5~.

Đơn ~[2, 3]~ có ~6~ cặp: ~(6, 4), (6, 9), (6, 10), (6, 15), (4, 10), (9, 15)~. Đơn ~[3, 10^6]~ có ~4~ cặp: ~(6, 9), (6, 15), (9, 15), (10, 15)~. Đơn ~[4, 10]~ chỉ có cặp ~(10, 15)~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Sáng sớm ở chợ nổi Cái Răng, ~N~ chiếc ghe hàng đậu thành một hàng dài dọc bờ sông, đánh số từ ~1~ đến ~N~ theo thứ tự. Trên mỗi ghe có một cây bẹo – cây sào dựng đứng treo mẫu hàng ghe đó bán để khách nhìn từ xa là biết. Cây bẹo của ghe thứ ~i~ cao ~h_i~.

Thầy Sơn mang máy ảnh ra chợ để làm tư liệu cho học trò. Mỗi tấm ảnh thầy chụp đúng một dãy ghe liên tiếp từ ghe ~l~ đến ghe ~r~ ~(1 \le l \le r \le N)~. Mỗi ghe chiếm đúng ~1~ đơn vị bề ngang. Khung ảnh phải đủ rộng để lấy hết các ghe và đủ cao để lấy trọn cây bẹo cao nhất. Do đó khung ảnh của dãy ~[l, r]~ có diện tích

~S(l, r)~ ~= (r - l + 1) \times \max(h_l, h_{l+1}, \ldots, h_r).~

Có tất cả ~\frac{N(N+1)}{2}~ cách chọn dãy ghe. Thầy Sơn tính diện tích khung ảnh của mọi dãy rồi xếp các diện tích theo thứ tự không giảm. Hai dãy khác nhau có cùng diện tích vẫn được tính là hai tấm. Tiệm in ảnh trên bờ chỉ còn đủ giấy để in tấm thứ ~K~ trong danh sách đó. Hãy giúp thầy Sơn biết tấm ảnh thứ ~K~ có diện tích bằng bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, K~ ~(1 \le N \le 3 \times 10^5,~ ~1 \le K \le \frac{N(N+1)}{2})~.
• Dòng thứ hai chứa ~N~ số nguyên ~h_1, h_2, \ldots, h_N~ ~(1 \le h_i \le 10^9)~.

Kết quả

Một số nguyên duy nhất là diện tích thứ ~K~ (theo thứ tự không giảm) trong các diện tích khung ảnh.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 2000~.
• Subtask 2 (~30\%~ số điểm): ~K \le 10^6~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 4 giây.

Sample Input 1

4 6
3 1 4 2

Sample Output 1

8

Giải thích

Có ~10~ dãy ghe:

• Dãy 1 ghe: ~[1,1], [2,2], [3,3], [4,4]~ có diện tích ~3, 1, 4, 2~.
• Dãy 2 ghe: ~[1,2]~ có diện tích ~2 \times 3 = 6~; ~[2,3]~ và ~[3,4]~ đều có ~2 \times 4 = 8~.
• Dãy 3 ghe: ~[1,3]~ và ~[2,4]~ đều có ~3 \times 4 = 12~.
• Dãy 4 ghe: ~[1,4]~ có ~4 \times 4 = 16~.

Xếp không giảm: ~1, 2, 3, 4, 6, 8, 8, 12, 12, 16~. Tấm thứ ~6~ có diện tích ~8~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Gần Tết, thầy Sơn về phụ ba mẹ làm bảng hiệu mới cho chiếc ghe bán trái cây ở chợ nổi Phong Điền. Trong thùng đồ nghề có một dải chữ cái gỗ được xếp sẵn thành một hàng, đọc từ trái sang phải là xâu ~S~ gồm ~n~ chữ cái latin thường.

Thầy Sơn sẽ chọn ra một số chữ cái (ít nhất một chữ) trong dải, giữ nguyên thứ tự trái sang phải của chúng, rồi ghép lại thành dòng chữ trên bảng hiệu. Nói cách khác, dòng chữ là một xâu con (không nhất thiết liên tiếp) của ~S~. Hai cách chọn được coi là khác nhau nếu tập vị trí các chữ được chọn khác nhau, kể cả khi dòng chữ thu được giống nhau.

Dân buôn bán trên sông rất kiêng chữ "lỗ". Má thầy Sơn dặn: dòng chữ trên bảng hiệu tuyệt đối không được chứa xâu ~P~ (gồm ~m~ chữ cái latin thường) như một đoạn liên tiếp. Ví dụ với ~P =~ lo, dòng chữ olol không được phép vì có đoạn lo ở giữa, còn dòng chữ oll thì được phép.

Hãy giúp thầy Sơn đếm số cách chọn hợp lệ. Vì kết quả có thể rất lớn, chỉ cần in ra phần dư khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu tiên chứa xâu ~S~ ~(1 \le n = |S| \le 10^5)~.
• Dòng thứ hai chứa xâu ~P~ ~(1 \le m = |P| \le 100)~.

Cả hai xâu chỉ gồm các chữ cái latin thường từ a đến z.

Kết quả

Một số nguyên duy nhất là số cách chọn hợp lệ, lấy phần dư khi chia cho ~10^9 + 7~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~n \le 20~.
• Subtask 2 (~30\%~ số điểm): các chữ cái của ~P~ đôi một khác nhau.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

lolo
lo

Sample Output 1

7

Giải thích

Có ~2^4 - 1 = 15~ cách chọn. Các cách hợp lệ là: ~4~ cách chọn một chữ; chọn vị trí ~\{1, 3\}~ được ll, ~\{2, 3\}~ được ol, ~\{2, 4\}~ được oo. Mọi cách chọn khác đều tạo ra dòng chữ chứa lo (chẳng hạn ~\{1, 2\}~ được lo, ~\{2, 3, 4\}~ được olo). Vậy có ~7~ cách.

Sample Input 2

ababa
aba

Sample Output 2

22

Giải thích

Có ~2^5 - 1 = 31~ cách chọn, trong đó có ~9~ cách cho dòng chữ chứa đoạn aba:

• ~4~ cách cho đúng aba: vị trí ~\{1,2,3\}, \{1,2,5\}, \{1,4,5\}, \{3,4,5\}~;
• ~\{1,2,3,4\}~ → abab, ~\{1,2,3,5\}~ → abaa, ~\{1,3,4,5\}~ → aaba, ~\{2,3,4,5\}~ → baba, ~\{1,2,3,4,5\}~ → ababa.

Mỗi tập vị trí chỉ được tính một lần. Đáp án là ~31 - 9 = 22~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cù lao Tân Lộc giữa sông Hậu có ~N~ ấp, đánh số từ ~1~ đến ~N~. Ấp nọ cách ấp kia bởi những con rạch nhỏ, nên muốn qua lại thì phải bắc cầu khỉ. Năm nay xã giao cho thầy Sơn lập phương án bắc cầu khỉ cho cả cù lao.

Thầy Sơn làm việc rất cẩn thận: trong ~Q~ ngày, mỗi ngày thầy ghi vào sổ một phương án mới — là một danh sách các cây cầu, xếp theo đúng thứ tự được thêm vào. Phương án của ngày ~0~ là danh sách rỗng (chưa có cầu nào). Phương án của ngày ~i~ ~(1 \le i \le Q)~ được lập theo một trong ba cách:

• 1 u v: chép lại phương án ngày ~i-1~ rồi thêm vào cuối một cây cầu nối ấp ~u~ với ấp ~v~ ~(u \ne v)~. Có thể giữa ~u~ và ~v~ đã có cầu, hoặc đã đi lại được với nhau từ trước.
• 2 t: chép lại phương án ngày ~i-1~ rồi bỏ đi ~t~ cây cầu được thêm sau cùng của phương án đó (dữ liệu bảo đảm phương án ngày ~i-1~ có ít nhất ~t~ cây cầu).
• 3 k: lấy lại y nguyên phương án của ngày ~k~ ~(0 \le k < i)~ — kể cả thứ tự các cây cầu.

Cuối mỗi ngày, thầy Sơn muốn biết phương án vừa lập "tốt" tới đâu: có bao nhiêu cặp ấp ~\{x, y\}~ ~(x < y)~ mà người dân có thể đi từ ấp ~x~ tới ấp ~y~ chỉ bằng các cây cầu trong phương án của ngày hôm đó.

Hãy giúp thầy Sơn trả lời cho cả ~Q~ ngày.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(2 \le N \le 2 \times 10^5;~ ~1 \le Q \le 2 \times 10^5)~.
• Dòng thứ ~i~ trong ~Q~ dòng tiếp theo mô tả phương án ngày ~i~, có một trong ba dạng 1 u v ~(1 \le u, v \le N,\ u \ne v)~, 2 t ~(t \ge 1)~ hoặc 3 k ~(0 \le k < i)~ như mô tả ở trên.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~i~ là số cặp ấp đi lại được với nhau theo phương án của ngày ~i~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N, Q \le 2000~.
• Subtask 2 (~20\%~ số điểm): chỉ có các phương án dạng 1 u v.
• Subtask 3 (~25\%~ số điểm): chỉ có các phương án dạng 1 u v và 2 t.
• Subtask 4 (~35\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

5 8
1 1 2
1 2 3
1 4 5
2 2
3 3
1 3 1
2 3
3 5

Sample Output 1

1
3
4
1
4
4
1
4

Giải thích

• Ngày 1 (1 1 2): cầu (1–2); các nhóm {1, 2}; số cặp: 1.
• Ngày 2 (1 2 3): cầu (1–2), (2–3); các nhóm {1, 2, 3}; số cặp: 3.
• Ngày 3 (1 4 5): cầu (1–2), (2–3), (4–5); các nhóm {1, 2, 3}, {4, 5}; số cặp: 3 + 1 = 4.
• Ngày 4 (2 2): cầu (1–2); các nhóm {1, 2}; số cặp: 1.
• Ngày 5 (3 3): cầu (1–2), (2–3), (4–5); các nhóm {1, 2, 3}, {4, 5}; số cặp: 4.
• Ngày 6 (1 3 1): cầu (1–2), (2–3), (4–5), (3–1); các nhóm {1, 2, 3}, {4, 5}; số cặp: 4.
• Ngày 7 (2 3): cầu (1–2); các nhóm {1, 2}; số cặp: 1.
• Ngày 8 (3 5): cầu (1–2), (2–3), (4–5); các nhóm {1, 2, 3}, {4, 5}; số cặp: 4.

Ngày 7 bỏ đi ~3~ cây cầu được thêm sau cùng của phương án ngày 6, đó là (3–1), (4–5), (2–3).

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Sáng sớm, chợ nổi Cái Răng có ~N~ chiếc ghe đậu thành một hàng dài dọc theo bờ sông, đánh số từ ~1~ đến ~N~ tính từ phía cầu. Ghe thứ ~i~ chỉ bán đúng một loại trái cây, có mã loại là ~a_i~ (các ghe khác nhau có thể bán cùng một loại).

Thầy Sơn dẫn học trò đi thực tế môn "Kinh tế gia đình". Mỗi nhóm học trò sẽ được giao một đoạn ghe liên tiếp ~[l, r]~ ~(l \le r)~, chèo xuồng ghé lần lượt từ ghe ~l~ tới ghe ~r~ để hỏi giá. Bài tập của thầy là: với mỗi loại trái cây gặp được, hãy so sánh giá giữa các ghe bán loại đó. Vì vậy thầy gọi đoạn ~[l, r]~ là so giá được nếu mọi loại trái cây có mặt trong đoạn đều được bán bởi ít nhất hai ghe trong đoạn. Chẳng hạn, đoạn có các loại ~3, 5, 3, 5, 5~ là so giá được, còn đoạn ~3, 5, 3~ thì không (loại ~5~ chỉ có một ghe, không có gì để so).

Thầy Sơn có ~Q~ câu hỏi. Câu hỏi thứ ~j~ cho hai số ~L_j, R_j~: hỏi có bao nhiêu cặp ~(l, r)~ với ~L_j \le l \le r \le R_j~ mà đoạn ghe ~[l, r]~ là so giá được?

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N, Q \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~.
• ~Q~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~L_j, R_j~ ~(1 \le L_j \le R_j \le N)~.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~j~ là câu trả lời cho câu hỏi thứ ~j~.

Giới hạn (Subtask)

• Subtask 1 (~10\%~ số điểm): ~N, Q \le 100~.
• Subtask 2 (~20\%~ số điểm): ~N \le 3000~.
• Subtask 3 (~20\%~ số điểm): ~Q \le 5~.
• Subtask 4 (~20\%~ số điểm): ~L_j = 1~ với mọi ~j~.
• Subtask 5 (~30\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây.

Sample Input 1

8 3
7 5 3 5 5 5 3 3
1 8
2 7
3 6

Sample Output 1

10
5
3

Giải thích

Có ~10~ đoạn so giá được trong cả hàng ghe: ~[2, 7]~ (5 3 5 5 5 3), ~[2, 8]~, ~[3, 7]~, ~[3, 8]~, ~[4, 5]~ (5 5), ~[4, 6]~, ~[4, 8]~ (5 5 5 3 3), ~[5, 6]~, ~[5, 8]~ và ~[7, 8]~ (3 3).

• Câu hỏi ~[2, 7]~: có ~5~ đoạn ~[2, 7]~, ~[3, 7]~, ~[4, 5]~, ~[4, 6]~, ~[5, 6]~.
• Câu hỏi ~[3, 6]~: có ~3~ đoạn ~[4, 5]~, ~[4, 6]~, ~[5, 6]~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).