Масив 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
Після першого запиту перестановка має вигляд (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). Вся перестановка непарна.