Закусити#12875

Закусити

Масив a_1, a_2, \ldots, a_m цілих чисел називається непарним, якщо в ньому непарна кількість інверсій, і парним в іншому випадку. Нагадаємо, що інверсія  — це пара з 1 \le i < j \le m така, що a_i>a_j. Наприклад, в масиві [2, 4, 1, 3] інверсії: (1, 3), (2, 3), (2, 4) (оскільки a_1>a_3, a_2>a_3, a_2>a_4), тому він непарний.

Для перестановки p_1, p_2, \ldots, p_n чисел від до назвемо її красою довжину її найдовшої непарної підпослідовності, якщо така існує, а інакше . Наприклад, краса перестановки (1, 2, 3) рівна , адже кожна її підпослідовність парна, краса (4, 1, 2, 3) рівна , адже вся перестановка є непарною, а краса (4, 1, 3, 2) рівна , адже вся перестановка є парною, а підпослідовність (4, 3, 2) є непарною.

Нам дана початкова перестановка p_1, p_2, \ldots, p_n. До неї буде запитів оновлення. Після -го запиту ми матимемо обміняти місцями p_{u_i} та p_{v_i}.

Знайдіть красу перестановки після кожного запиту.

Нагадаємо, що масив є підпослідовністю , якщо можна отримати з видаленням кількох (можливо, жодного або всіх) елементів.

Нагадаємо, що перестановка чисел від до  — це масив довжини , що містить кожне число від до рівно один раз.

Вхідні дані

Перший рядок містить два цілих числа (1 \le n, q \le 2\cdot 10^5)  — довжину перестановки та кількість запитів відповідно.

Наступний рядок містить цілих чисел p_1, p_2, \ldots, p_n (1 \le p_i \le n, всі p_i попарно різні)  — початкову перестановку .

-ий з наступних рядків містить два цілих числа u_i, v_i (1 \le u_i, v_i \le n, u_i \neq v_i), позначаючі, що після -го запиту ви маєте обміняти місцями p_{u_i} та p_{v_i}.

Вихідні дані

Виведіть чисел  — красу перестановки після кожного запиту оновлення.

Приклади

Приклад 1

Loading
Loading

Примітка

  • Після першого запиту перестановка має вигляд (1, 2, 3, 4, 5). В ній нема жодної непарної підпослідовності.

  • Після другого запиту перестановка має вигляд (2, 1, 3, 4, 5). Вся перестановка непарна, адже в ній рівно одна інверсія.

  • Після третього запиту перестановка має вигляд (4, 1, 3, 2, 5). Вся перестановка парна, але її підпослідовність (4, 3, 2, 5) непарна.

  • Після четвертого запиту перестановка має вигляд (1, 4, 3, 2, 5). Вся перестановка непарна.

  • Після п'ятого запиту перестановка має вигляд (1, 4, 5, 2, 3). Вся перестановка парна, і всі її підпослідовності довжини парні, але підпослідовність (1, 5, 2) непарна.

  • Після шостого запиту перестановка має вигляд (5, 4, 1, 2, 3). Вся перестановка непарна.