У Игоря была последовательность \(d_1, d_2, \dots, d_n\). Когда Игорь зашёл в класс, на доске было записано число \(x\).
Игорь создал последовательность \(p\) по следующему алгоритму:
- сначала, \(p = [x]\);
- для каждого \(1 \leq i \leq n\) он сделал следующую операцию \(|d_i|\) раз:
- если \(d_i \geq 0\), он посмотрел на последний элемент \(p\) (назовём его \(y\)) и записал \(y + 1\) в конец \(p\);
- если \(d_i < 0\), он посмотрел на последний элемент \(p\) (назовём его \(y\)) и записал \(y - 1\) в конец \(p\).
Например, если \(x = 3\), \(d = [1, -1, 2]\), последовательность \(p\) будет равна \([3, 4, 3, 4, 5]\).
Игорь решил посчитать длину наибольшей возрастающей подпоследовательности \(p\) и их количество.
Последовательность \(a\) является подпоследовательностью \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) элементов.
Последовательность \(a\) является возрастающей, если каждый элемент \(a\) (кроме первого) строго больше предыдущего.
При \(p = [3, 4, 3, 4, 5]\) длина наибольшей возрастающей подпоследовательности равна \(3\), а их количество равно \(3\): \([\underline{3}, \underline{4}, 3, 4, \underline{5}]\), \([\underline{3}, 4, 3, \underline{4}, \underline{5}]\), \([3, 4, \underline{3}, \underline{4}, \underline{5}]\).
Примечание
Первый пример разобран в условии.
Во втором примере \(p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108]\).
В третьем примере \(p = [1, 2, \ldots, 2000000000]\).