Đặt:

• ~dp[i]~: số cách chia dãy ~a_1, a_2, \ldots, a_i~ thành các dãy đẹp liên tiếp.
• ~dp[0] = 1~
• ~beauty(j, i)~: đoạn ~a_j, a_{j + 1}, \ldots, a_i~ là dãy đẹp, tức là số bước bubble sort không quá ~k~ lần.
• Với mỗi ~i~, nếu ~1 \le j \le i~ và ~beauty(j, i)~ thì số cách chia dãy ~a_1, a_2, \ldots, a_i~ thành các dãy đẹp liên tiếp sao cho dãy cuối cùng là dãy ~a_j, a_{j + 1}, \ldots, a_i~ bằng ~dp[j - 1]~.
• Công thức tổng quát: ~dp[i] = \sum_{1 \le j \le i, beauty(i, j)}dp[j - 1]~

Kết quả của bài toán là: ~dp[n]~.

Vậy làm sao để tính ~beauty(l, r)~ hay làm sao kiểm tra đoạn ~a_l, a_{l + 1}, \ldots, a_r~ có là dãy đẹp hay không?

~\textbf{Subtask 1:}~

Để tính ~beauty(l, r)~, mô phỏng lại chính xác thuật toán được mô tả ở đề bài.

Với dãy độ dài ~m~, thuật toán bubble sort được miêu tả trong đề bài có độ phức tạp là ~O(m^2)~ hoặc ~O(m^3)~ tùy theo cách cài đặt.

Dãy ~a_1, a_2, \ldots, a_n~ có ~O(n^2)~ dãy con.

Độ phức tạp: ~O(n^4)~ hoặc ~O(n^5)~ tùy theo cách cài đặt.

~\textbf{Subtask 2:}~

Nhận xét: số bước trong bubble sort chính là số cặp nghịch thế.

Cặp ~(i, j)~ gọi là nghịch thế nếu ~i < j~ và ~a_i > a_j~.

Để đếm số nghịch thế của ~a_l, a_{l + 1}, \ldots, a_r~, tái sử dụng kết quả từ ~a_l, a_{l + 1}, \ldots, a_{r - 1}~

• Giả sử biết số nghịch thế trong đoạn ~a_l, a_{l + 1}, \ldots, a_{r - 1}~ là ~inv[l][r - 1]~.
• Khi thêm phần tử ~a_r~ vào cuối đoạn, chỉ có thể tạo cặp nghịch thế mới giữa các phần tử trước đó và phần tử ~a_r~.
• ~inv[l][r] = inv[l][r - 1] + |\{i | i \in [l, r - 1] \land a_i > a_r\}|~. Trong đó, ~|\{i | i \in [l, r - 1] \land a_i > a_r\}|~ là số lượng các phần tử trước đó trong dãy tạo thành cặp nghịch thế với phần tử ~a_r~

Việc tính số lượng cặp nghịch thế của một dãy dựa trên kết quả của các dãy trước đó tốn độ phức tạp ~O(n)~.

Độ phức tạp: ~O(n^3)~.

~\textbf{Subtask 3:}~

Nhận xét: Nếu ~beauty(j, i)~ thì ~beauty(j + 1, i)~, tức là nếu dãy ~a_j, a_{j + 1}, \ldots, a_i~ là dãy đẹp thì dãy ~a_{j + 1}, a_{j + 2}, \ldots, a_i~ cũng là dãy đẹp vì bỏ đi một phần tử không làm tăng số nghịch thế.

Đặt:

• ~best[i]~ là giá trị nhỏ nhất sao cho ~beauty(best[i], i)~.
• ~1 \le best[i] \le i~.
• ~best[1] \le best[2] \le \ldots \le best[n]~ do ~beauty(best[i], i) \to beauty(best[i], i - 1)~ nên ~best[i - 1] \le best[i]~.

Công thức quy hoạch động mới: ~dp[i] = \sum_{best[i] \le j \le i} dp[j - 1]~

Do ~best[1] \le best[2] \le \ldots \le best[n]~ nên ta có thể sử dụng kĩ thuật hai con trỏ để tính mảng ~best~:

• Gọi ~inv~ là số lượng cặp nghịch thế trong đoạn ~a_{best[i]}, a_{best[i] + 1}, \ldots, a_i~.
• Nếu ~inv > k~ thì cập nhật lại ~best[i] += 1~.
• Khi thêm/xóa phần tử, duyệt qua các phần tử còn lại trong dãy con để cập nhật giá trị ~inv~.

Độ phức tạp: ~O(n^2)~.

~\textbf{Subtask 4:}~

Ở phần tính toán mảng ~best~, khi thêm/xóa phần tử, có thể sử dụng cấu trúc dữ liệu ~\textbf{Fenwick Tree}~ để đếm số lượng phần tử còn lại trong dãy con mà tạo cặp nghịch thế với phần tử vừa được thêm/xóa.

Do mảng ~dp~ được tính theo thứ tự ~dp[1], dp[2], \ldots dp[n]~, có thể sử dụng tổng cộng dồn để tối ưu việc chuyển trạng thái.