\(N\) осіб під номерами \(1,2, \dots ,N\) стоять у ряду. Особа \(i\) носить колір \(A_i\).

Відповідайте на \(Q\) запитів у форматі, наведеному нижче.

• Вам задано цілі числа \(l\) і \(r\). Враховуючи лише осіб \(l,l+1, \dots ,r\), скільки максимально можна отримати таких пар людей , що одягнені в одяг однакового кольору?

Обмеження

• Усі значення у вхідних даних є цілими числами.

• \(1 \le N \le 10^5\)

• \(1 \le Q \le 10^6\)

• \(1 \le A_i \le N\)

• \(1 \le l \le r \le N\).

Формат вхідних даних

Перший рядок містить ціле число \(N\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\)

Третій рядок містить ціле число \(Q\)

Наступні  \(Q\) рядків містять запити: цілі числа \(l, r\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

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

Примітка

До прикладу 1:

Маємо \(A=(1,2,3,2,3,1,3,1,2,3)\). Цей вхід містить шість запитів.

Перший запит: (l, r) = (6, 10). Поєднавши 6, 8 і 7, 10, ми можемо сформувати дві пари людей одного кольору.

Другий запит: (l, r) = (5, 8). Об’єднавши в пари 5, 7 і 6, 8, ми можемо сформувати дві пари людей одного кольору.

Може бути запит, де l=r.

Приклад вхідних даних

10
1 2 3 2 3 1 3 1 2 3
6
6 10
5 8
3 6
4 4
1 6
1 10

Приклад вихідних даних

2
2
1
0
3
4