Yana, Mino, White và Huzz là những người bạn thân nhất của nhau.
Sau khi cuối cùng cũng hoàn thành xong những nhiệm vụ khắt khe của huấn luyện viên, Huzz đã có được một khoảng nghỉ ngơi. Cậu tìm thấy sự thư thái ấy vào một buổi chiều lười biếng, khi thế giới dường như chậm lại, được bao bọc trong màn sương ấm áp ánh vàng của buổi hoàng hôn sắp buông. Một làn gió nhẹ chỉ đủ làm khẽ lay động những hạt bụi đang nhảy múa trong những tia nắng xiên qua tán lá của một cây sồi lớn.
Trong khoảng không êm đềm và ngái ngủ ấy, Huzz tìm thấy một hoán vị trong món đồ chơi cá mập mềm mại của mình. Cậu quyết định chia sẻ nó với những người bạn của mình cho vui.
Mino thích chia tách. Cậu có thể chia hoán vị này thành một số đoạn liên tiếp.
Yana thích hoán đổi. Cậu có thể chọn một đoạn liên tiếp và hoán đổi phần tử lớn nhất với phần tử nhỏ nhất của nó.
Cụ thể, họ có thể thực hiện hai loại thao tác sau với số lần bất kỳ, theo thứ tự bất kỳ:
- split: Chọn một đoạn liên tiếp có độ dài lớn hơn $1$. Sau đó chọn một vị trí bên trong nó và chia nó thành hai đoạn liên tiếp kề nhau. Ví dụ, $(a_i, \dots, a_j)$ có thể được chia thành $(a_i, \dots, a_k)$ và $(a_{k+1}, \dots, a_j)$, trong đó $i \le k < j$.
- swap: Chọn một đoạn liên tiếp và hoán đổi phần tử lớn nhất với phần tử nhỏ nhất của nó.
Sau khi thực hiện một số lần thao tác bất kỳ, họ dừng lại, và tất cả các đoạn thu được sẽ được gộp lại theo thứ tự ban đầu để tạo thành một hoán vị mới.
White thích đếm. Cô tự hỏi — họ có thể thu được bao nhiêu hoán vị phân biệt?
Vì kết quả có thể rất lớn, bạn chỉ cần tìm đáp án theo modulo $998\,244\,353$.
Dữ liệu
Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 500$), độ dài của hoán vị.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), biểu thị bản thân hoán vị đó. Dữ liệu đảm bảo $\{a_n\}$ là một hoán vị.
Kết quả
In ra một số nguyên là số lượng hoán vị phân biệt mà họ có thể thu được theo modulo $998\,244\,353$.
Ví dụ
Dữ liệu
4 1 4 2 3
Kết quả
10
Dữ liệu
7 5 1 4 2 6 3 7
Kết quả
340
Giải thích
Ở ví dụ đầu tiên, dưới đây là tất cả các hoán vị có thể mà họ thu được:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$