Важка робота волонтерів
Обмеження: 3 сек., 256 МіБ
Тисячі волонтерів щоденно допомагають українським воїнам виконувати їхню роботу.
Зеник — один з таких волонтерів. Він займається перевезеннями посилок вздовж лінії фронту. Позиції на лінії фронту пронумеровані цілими числами від 0 до 109. Зеник вже спланував свій маршрут на сьогодні. Зараз він знаходиться у позиції з номером 0, далі він поїде у позицію з номером x1, потім звідти у позицію з номером x2 і так далі, аж доки не закінчить свою роботу на сьогодні у позиції xn. Позиції x1, x2, …, xn Зеник називає ключовими, але їдучи з одної ключової позиції у іншу, він також відвідує усі проміжні позиції між ними.
Зенику відомо про m посилок, які треба перевезти. i-ту посилку треба доставити з позиції з номером ai у позицію з номером bi. Відвідуючи якусь позицію Зеник підбирає усі посилки, які треба передати з цієї позиції та віддає усі посилки, які він вже підібрав, що адресуються сюди. Цікаво, скільки посилок Зеник зможе доставити сьогодні?
Вхідні дані
У першому рядку задано два цілих числа через пробіл — n та m — кількість ключових позицій та кількість посилок, про які відомо Зенику.
У другому рядку задано n цілих чисел через пробіл — номери ключових позицій, які відвівутиме Зеник.
У наступних m рядках задано по два цілих числа — ai та bi — звідки і куди треба доставити i-ту посилку.
Вихідні дані
Одне число — кількість посилок, які доставить Зеник.
Обмеження
1≤n,m≤105,
0≤xi,ai,bi≤109, ai≠bi.
Оцiнювання задачi складається iз наступних блокiв:
1 бал — приклад з умови,
4 бали — блок тестів у яких n,m,xi,ai,bi≤100.
10 балів — блок тестів у яких n,m≤1000.
10 балів — блок тестів без додаткових обмежень.
Бали за блок ви отримаєте, лише якщо дасте правильну вiдповiдь на всi тести з блоку.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
3 3 7 4 7 2 4 7 5 6 3 | 2 |
Примітки
Спочатку Зеник підбере першу посилку у позиції 2. У позиції 4 Зеник віддасть першу посилку. Далі Зеник підбере третю та другу посилки у позиціях 6 та 7 відповідно. Прямуючи до настпуної ключової позиції (з номером 4), Зеник зможе віддати другу посилку у позиції 5. На шляху від позиції 4 до 7 вже не буде посилок, які треба підбирати чи віддавати. Нагоди віддати третю посилку у Зеника нема.