Танцюючі слони#2256
Dancing Elephants — це видовищне шоу в Паттаї, у якому бере участь слонів, що виступають в одному ряді, який називають сценою.
Після багатьох років тренувань слони опанували численні танцювальні рухи. Кожне шоу складається з послідовності актів: у кожному з них один слон виконує танцювальний рух, можливо змінюючи свою позицію на сцені.
Продюсери шоу прагнуть створити фотоальбом, що відображає все шоу. Вони планують фотографувати всіх слонів після кожного акту.
У будь-який момент під час шоу деякі слони можуть стояти на одній і тій самій позиції, тобто бути просто поряд один з одним.
Одна камера може сфотографувати групу слонів лише тоді, коли всі їхні позиції знаходяться в межах відрізка довжини (включно з обома межами відрізка). Оскільки слони можуть бути розкидані по сцені, можливо, знадобиться кілька камер, щоб сфотографувати всіх слонів одночасно.
Наприклад, якщо l = 10, а слони знаходяться у позиціях , , та , у цьому випадку достатньо однієї камери, щоб сфотографувати всіх слонів, як показано нижче (слони зображені трикутниками, камери — трапеціями).
У наступному акті слон на позиції переміщується на позицію . Після цього для фотографування всіх слонів одночасно потрібно принаймні дві камери.
У наступному акті слон на позиції переміщується на позицію . У цьому випадку необхідно вже камери, щоб сфотографувати всіх слонів.
Ваше завдання — визначити мінімальну кількість камер, необхідних, щоб сфотографувати всіх слонів після кожного акту.
У першому рядку задано три невід'ємних цілих числа , , (0 \leq n \leq 15 \cdot 10^4, 0 \leq l \leq 10^9, 0 \leq m \leq 15 \cdot 10^4).
У наступних рядках міститься по одному числу x_i, що означає позицію кожного слона (0 \leq x_i \leq 10^9). Усі початкові позиції відсортовані. Зауважте, що під час танцю порядок слонів може змінитися.
Наступні рядків містять по два цілих числа та , що означає: у відповідному акті слон з номером переміщується на позицію з координатою . Гарантовано, що задовольняє обмеження 0 \leq y \leq 10^9.
Виведіть рядків, у кожному з яких одне число — мінімальна кількість камер, необхідних для фотографування всіх слонів після відповідного акту.
Приклад 1