Дается массив \(A\) длины \(N\) и \(Q\) запросов. Для каждого запроса необходимо найти минимум в массиве \(A\) от \(l\) до \(r\).

Ввиду оптимизации чтения запросов, вам дается только первый запрос \(l_1, r_1\). Остальные запросы генерируются в зависимости от ответа на запрос (\(ans_{i}\) = минимум на подотрезке для запроса \(i\)). То есть \(ans_{1}\) = ответ на запрос \(l_1, r_1\). Тогда следующий запрос генерируется следующим образом: \(l_{i+1}=(l_i \oplus ans_i) \mod n + 1, r_{i + 1}=(r_i \oplus ans_i) \mod n + 1\). Если после операции \(l_{i + 1} > r_{i + 1}\), необходимо произвести операцию \(swap\), т.е. \(if (l > r)\) тогда \(swap(l, r)\).

Вам необходимо вывести сумму всех ответов, т.е. \(ans_1 + ans_2 + ... + ans_Q\)

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

В первой строке дается число \(N\) \((1 \leq N \leq 10^6)\). Во второй строке дается массив \(A\) длины \(N\), \((1 \leq i \leq N, 1 \leq a_i \leq 10^6)\). В следующей строке дается число \(Q\), \((1 \leq Q \leq 10^7)\). В следующей строке дается первый запрос \(l_1, r_1\) \((1 \leq l_1 \leq r_1 \leq N)\).

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

Вам необходимо вывести сумму всех ответов, т.е. \(ans_1 + ans_2 + ... + ans_Q\).

Примеры

Ввод 1

5
4 3 1 2 5
3
1 2

Ответ 1

5