Chọn ĐT HSG Đà Nẵng 2026 (Thi thử của NBK & LTT) Day 2

Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử của dãy ban đầu (có thể không xóa phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại.

Một dãy số được gọi là dãy tăng kép nếu có thể tách nó ra thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng một trong hai dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên \(a\) có \(n\) phần tử, hãy đếm số dãy con của \(a\) là dãy tăng kép.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq n\)).

Output

• In ra số lượng dãy tăng kép là dãy con của \(a\), sau khi chia lấy dư cho \(10^9+7\).

Example

4
3 3 4 2

9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 200\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 2000\) và \(a_i \leq 200\).
• Subtask \(4\) (\(35\%\) số điểm): \(n \leq 2000\).

An có một người bạn điều hành một quầy giải khát trong căn tin. Người bạn này sẽ bán đồ uống trong \(n\) ngày, được đánh số từ ngày \(1\) đến ngày \(n\). Có tất cả \(m\) loại đồ uống, được đánh số từ \(1\) đến \(m\).

Lợi nhuận thu được từ việc bán một loại đồ uống vào một ngày cụ thể có thể thay đổi. Vào ngày \(i\), lợi nhuận dự kiến từ việc bán đồ uống loại \(j\) là \(A_{ij}\). Lưu ý rằng \(A_{ij}\) có thể âm, nghĩa là việc bán loại đồ uống đó thực tế sẽ gây lỗ.

An muốn giúp bạn mình lập kế hoạch bán hàng trong \(n\) ngày. Mỗi ngày, An phải chọn bán ít nhất một loại đồ uống. Đồng thời, các loại đồ uống được chọn trong cùng một ngày phải là những loại đứng liên tiếp nhau. Nói cách khác, ở mỗi ngày, An sẽ chọn hai chỉ số \(l\) và \(r\) sao cho \(1\le l\le r\le m\) rồi bán tất cả các loại đồ uống từ \(l\) đến \(r\).

Tuy nhiên, để đảm bảo khách hàng từ ngày hôm trước tiếp tục quay lại, việc lựa chọn các loại đồ uống được bán ở ngày \(i\) (\(i>1\)) phải đáp ứng các điều kiện sau:

• Có ít nhất một loại đồ uống cũng được bán trong ngày \(i-1\).
• Có ít nhất một loại đồ uống không được bán trong ngày \(i-1\).

Lợi nhuận hàng ngày là tổng lợi nhuận của tất cả các loại đồ uống được bán trong ngày đó. Tổng lợi nhuận của cả kế hoạch bán hàng là tổng lợi nhuận của \(n\) ngày.

Yêu cầu: Hãy tính tổng lợi nhuận tối đa có thể đạt được nếu An lập kế hoạch bán hàng một cách tối ưu.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1\le n\le 2\cdot 10^5\); \(3\le m\le 2\cdot 10^5\); \(n\cdot m\le 10^6\)) — số ngày và số loại đồ uống.
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên \(A_{ij}\) (\(-10^9 \le A_{ij} \le 10^9\)) — lợi nhuận của từng loại đồ uống.

Output

• In ra một số nguyên duy nhất là lợi nhuận tối đa có thể đạt được.

Example

3 6
79 20 49 5 -1000 500
-105 9 109 24 -98 -499
14 47 12 39 23 50

475

Ràng buộc

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài thỏa mãn \(n\le 50\); \(3\le m\le 30\).
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn \(n\le 2000\); \(3\le m\le 200\).
• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài không có ràng buộc gì thêm.

Trung tâm điều hành của một quốc gia đang quản lý một hệ thống truyền tin gồm \(n\) trạm, được đánh số từ \(1\) đến \(n\). Giữa một số cặp trạm có các tuyến cáp quang kết nối trực tiếp với nhau. Hệ thống này được mô hình hóa bởi một đồ thị vô hướng liên thông gồm \(n\) đỉnh và \(m\) cạnh.

Mỗi cạnh \((u, v)\) biểu diễn một tuyến cáp nối trực tiếp hai trạm \(u\) và \(v\).

Do yêu cầu an ninh, người ta muốn xác định những tuyến cáp đặc biệt trọng yếu: đó là các tuyến mà nếu đồng thời loại bỏ cả hai trạm ở hai đầu tuyến cáp đó cùng toàn bộ các tuyến liên quan đến chúng, thì phần còn lại của hệ thống sẽ không còn liên thông.

Yêu cầu

Hãy đếm số cạnh \((u, v)\) của đồ thị sao cho khi xóa hai đỉnh \(u, v\) và tất cả các cạnh kề với chúng, đồ thị còn lại trên \(n - 2\) đỉnh không liên thông.

Input

• Dòng đầu chứa hai số nguyên \(n, m\) (\(4 \le n \le 100000\), \(n - 1 \le m \le 300000\)) là số đỉnh và số cạnh của đồ thị.
• \(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(a_i, b_i\) (\(1 \le a_i, b_i \le n\)) cho biết có một cạnh nối giữa hai đỉnh \(a_i\) và \(b_i\).
• Đồ thị không có khuyên và không có cạnh trùng.

Output

• In ra một số nguyên duy nhất là số cạnh thỏa mãn điều kiện trên.

Example

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

1

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n \le 100, m \le 300\).
• Subtask 2 (\(20\%\) số điểm): \(n \le 1000, m \le 3000\).
• Subtask 3 (\(20\%\) số điểm): \(n \le 1000\).
• Subtask 4 (\(20\%\) số điểm): \(m - n \le 20\).
• Subtask 5 (\(20\%\) số điểm): Không có ràng buộc gì thêm.