\begin{tutorial}{Харухи и путешествие на круге}

Для удобства введем функцию $m(v)$ -- диаметрально противоположный сектор сектору $v$ и $dist(u, v)$ -- расстояние между 2 секторами без прыжков.

Идея 1. Не нужно прыгать больше одного раза.

Доказательство:

Пусть мы прыгнули больше одного раза, тогда мы прыгнули хотя бы 2 раза и часть пути будет состоять из переходов $u \to m(u) \to v \to m(v)$. Введем $c = m(v)$, тогда $v = m(c)$ и получаем путь $u \to m(u) \to m(c) \to c$, причем $dist(u, c) = dist(m(u), m(c))$, но тогда можно пойти напрямую из $u$ в $c$ и при этом сэкономить время: $dist(u, c) = dist(m(u), m(c)) < a_u + dist(m(u), m(c)) + a_{m(c)}$.

Из первой идеи следует, что нам достаточно рассмотреть единственный путь без прыжков и все пути ровно с одним прыжком. Будем далее считать, что мы совершаем ровно один прыжок. Если лучший ответ с одним прыжком $ans_1$, то ответом на запрос будет $\min (dist(u, v), ans_1)$.

Идея 2. Все пути ровно с одним прыжком можно рассмотреть с помощью 3 деревьев отрезков на минимум (далее ДО).

Построим 3 дерева отрезков:
\begin{enumerate}
\item ДО по массиву $a$.
\item ДО по массиву $b: b_i = a_i + 2 \cdot i$.
\item ДО по массиву $c: c_i = a_i - 2 \cdot i$.
\end{enumerate}

Для ответа на запрос $u, v$ поделим окружность на 4 части сегментами $u, v, m(u), m(v)$, причем сегменты делящие окружность можно отнести к любой из частей. Рассмотрим произвольный путь с 1 прыжком и начнем двигать место прыжка по часовой стрелке, то есть рассмотрим все пути вида $u \to c \to m(c) \to v$. Очевидно, что от $u$ до $c$ и от $m(c)$ до $v$ нужно идти по кратчайшему пути. Тогда временем затраченным на такой путь будет $f(c) = dist(u, c) + dist(m(c), v) + a_c$. При изменении $c$ на 1 изменения слагаемых $dist(u, c)$ и $dist(m(c), v)$ будет либо +1, либо -1, а значит эти слагаемые либо увеличат расстояние на 2, либо уменьшат на 2, либо не изменят сумму, а слагаемое $a_c$ просто зависит от $c$, но ведь это и есть 3 возможных поведения массивов, на которых построено ДО. Можно доказать, что внутри одной из четырех частей, на которые мы поделили окружнсоть, изменения $f$ будут соответствовать одному из 3 типов ДО, а реальное значение совпадать с точностью до константы, которую можно вычислить по заданным $u, v$. Самый простой способ вычислить константу без использования формул -- посчитать значение $f$ в одной точке каждой из частей и сравнить значение со значением в этой же точке в нужном типе ДО (выбор нужного типа ДО по точке оставляется как упражнение читателю), например, пусть $b_c = x$, $f(c) = y$, тогда внутри этой части будет выполняться $f(t) = b_t + (f(c) - b_c) = b_t + y - x$.

Доказательство того, что внутри одной из частей поведение не меняется:

Функция $dist(u, c)$ меняет поведение после прохождения точки $c = u$ и $c = m(u)$, а для $dist(m(c), v)$ после точек $m(c) = v$ и $m(c) = m(v)$, что равносильно $c = m(v)$ и $c = v$. Тогда получаем 4 точки: $u, v, m(u), m(v)$, после которых функция $dist(u, c) + dist(m(c), v)$ меняет поведение. Отсюда и следует неизменность поведения внутри одной из частей.

\end{tutorial}
