Запити на масиві

Обмеження: 2 сек., 256 МіБ

Задано масив $a$ з $n$ цілих чисел.

Елемент масиву $a_i$ є локальним максимумом, якщо $2 \le i \le n - 1$ і $a_{i-1} < a_i > a_{i+1}$.

Вам потрібно відповісти на $q$ запитів.

Запит задається цілим числом $x$. Для запиту ви повинні зробити операцію $a_i := a_i \mbox{ XOR } x$ для кожного елемента масиву. Після цього треба сказати кількість локальних максимумів у масиві.

Зауважте, що запити змінюють масив і є залежними між собою — наступний запит виконується після попередніх.

Вхідні дані

У першому рядку задано ціле число $n$ — довжину масиву.

У другому рядку задано $n$ цілих чисел $a_i$ — елементи масиву.

У третьому рядку задано ціле число $q$ — кількість запитів.

Наступні $q$ рядків містять по одному цілому числу $x$.

Вихідні дані

Виведіть $q$ рядків. В $i$-ому рядку виведіть ціле число — відповідь на $i$-ий запит.

Обмеження

$1 \le n \le 10^5$,

$1 \le a_i \le 10^9$,

$1 \le q \le 10^5$,

$0 \le x \le 10^9$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 1 3 1 5 9 7 11 5 10 3 4 7 11	2 3 2 2 2