시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB222100.000%

문제

Twoim zadaniem jest obliczenie liczby najdłuższych rosnących podciągów ciągu A modulo liczba m.

입력

W pierwszej linii wejścia znajdują się dwie liczby całkowite n i m (1 ≤ n ≤ 500 000, 1 ≤ m ≤ 109), odpowiednio długość ciągu A i liczba m. W następnym wierszu n liczb całkowitych - kolejne elementy ciągu A (0 ≤ ai ≤ 109) .

출력

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczę całkowitą - liczba najdłuższych rosnących podciągów modulo m.

예제 입력 1

4 10
3 2 5 4

예제 출력 1

4