D. Код Хаффмана на отрезке
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса хочет отправить важное сообщение Бобу. Сообщение a = (a1, ..., an) является последовательностью положительных чисел (символов).

Для сжатия сообщения Алиса хочет использовать двоичный код Хаффмана. Напомним, что двоичный код Хаффмана, или двоичный префиксно-свободный код — это функция f, которая сопоставляет каждому символу сообщения двоичные строки (то есть строки, состоящие только из символов «0» и «1») таким образом, что ни для какой пары различных символов ai и aj строка f(ai) не является префиксом f(aj) (и наоборот). Результатом кодирования сообщения a1, a2, ..., an является конкатенация кодов отдельных символов, то есть строка f(a1)f(a2)... f(an). Коды Хаффмана удобны тем, что закодированное сообщение можно легко и однозначно декодировать, если знать код. Код обычно выбирается таким образом, чтобы минимизировать суммарную длину закодированного сообщения, то есть длину строки f(a1)f(a2)... f(an).

Алиса не хочет посылать сообщение целиком, поскольку это слишком рискованно. Вместо этого она выбрала несколько частей сообщения и хочет отправить их по отдельности. Для каждой выбранной подстроки ali... ari она хочет найти минимальную длину этой подстроки, закодированной по Хаффману. Помогите ей с этой задачей.

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 100 000) — длина сообщения.

Во второй строке через пробел записано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 100 000) — символы сообщения.

В следующей строки записано одно целое число q (1 ≤ q ≤ 100 000) — количество запросов.

Следующие q строк описывают запросы, i-я из этих строк содержит два целых числа li и ri (1 ≤ li ≤ ri ≤ n) — позиции левого и правого конца i-й подстроки. Позиции нумеруются с 1. Подстроки могут перекрываться. Одна и та же подстрока может быть упомунята в нескольких запросах.

Выходные данные

Выведите q строк. Каждая строка должна содержать одно число — минимальную длину закодированной по Хаффману подстроки ali... ari.

Пример
Входные данные
7
1 2 1 3 1 2 1
5
1 7
1 3
3 5
2 4
4 4
Выходные данные
10
3
3
5
0
Примечание

В первом запросе, одним из оптимальных способов кодирования будет сопоставить символу 1 строку «0», символу 2 строку «10», а символу 3 строку «11».

Обратите внимание, что сопоставление пустой строки единственному символу является корректным кодом (как в пятом запросе из примера).