Dãy số hoàn hảo

View as PDF

Submit solution


Points: 0.56 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Dãy số ~A~ gồm ~n~ số nguyên khác nhau từng đôi: ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ được gọi là hoàn hảo nếu như nó thỏa mãn tính chất sau: "Không tồn tại ~3~ chỉ số ~p < q < r~ sao cho hoặc ~a_{p} < a_{q} < a_{r}~ hoặc ~a_{p} < a_{r} < a_{q}~ hoặc ~a_{q} < a_{p} < a_{r}~ ".

Cho ~A~ là dãy hoàn hảo, một phép chèn một số nguyên ~b~ vào dãy ~A~ để tạo thành dãy ~B~ ~(b~ có thể được chèn vào trước ~a_{1}~, hoặc giữa ~a_{i}~, ~a_{i + 1}~ với ~1 \leq i < n~, hoặc sau ~a_{n})~ được gọi là hợp lệ nếu như các điều kiện sau được thỏa mãn:

  • ~b > a_{i}~ với mọi ~1 \leq i \leq n~
  • Dãy ~B~ là hoàn hảo

Yêu cầu

  • Hãy tính số lượng phép chèn hợp lệ một số ~b~ vào dãy ~A~.
  • Giả sử ~B~ là một dãy thu được bởi một phép chèn hợp lệ ~b~ vào ~A~. Hãy tính số lượng dãy hoàn hảo thu được bằng cách hoán vị các phần tử của ~B~.

Input

  • Dòng thứ nhất chứa hai số nguyên ~n~ và ~b~ tương ứng với số lượng phần tử của dãy ~A~ và số nguyên cần chèn. Biết rằng ~3 \leq n \leq 10^{5}~, ~|b| \leq 10^{6}~.
  • Dòng thứ hai chứa ~n~ số nguyên ~a_{1}~, ~a_{2}~, ..., ~a_{n}~, mỗi số có trị tuyệt đối ~\leq 10^{6}~.
  • Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

  • Dòng thứ nhất ghi một số nguyên là số phép chèn hợp lệ số ~b~ vào dãy ~A~.
  • Dòng thứ hai ghi một số nguyên là phần dư trong phép chia cho ~10^{9}~ của số lượng dãy hoàn hảo thu được bằng cách hoán vị các phần tử của dãy ~B~. Nếu không thể chèn được ~b~ vào dãy ~A~, ta ghi ra ~0~.

Giới hạn

Có ~50\%~ số test có ~n \leq 15~.

Sample Input

4 2012
55 25 9 20

Sample Output

2
8

Comments

Please read the guidelines before commenting.


There are no comments at the moment.