C. Циклические RMQ
ограничение по времени на тест
1.5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Дан циклический массив a0, a1, ..., an - 1. Есть два типа операций:

  • inc(lf, rg, v) — увеличить каждый элемент на отрезке [lf, rg] (включительно) на v;
  • rmq(lf, rg) — найти минимальное значение на отрезке [lf, rg] (включительно).

Мы считаем, что все отрезки — циклические, например если n = 5 и lf = 3, rg = 1, то имеется в виду последовательность индексов: 3, 4, 0, 1.

Напишите программу, которая будет выполнять заданную последовательность операций.

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

Первая строка содержит целое число n (1 ≤ n ≤ 200000). Следующая строка описывает начальное состояние массива: a0, a1, ..., an - 1 ( - 106 ≤ ai ≤ 106), ai целые. Третья строка содержит целое число m (0 ≤ m ≤ 200000), m — количество операций. Следующие m строк описывают операции. Если строка содержит два целых числа lf, rg (0 ≤ lf, rg ≤ n - 1), то это она задает операцию rmq, а если она содержит три целых числа lf, rg, v (0 ≤ lf, rg ≤ n - 1; - 106 ≤ v ≤ 106) — операцию inc.

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

Для каждой операции rmq выведите ее результат. Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).

Примеры
Входные данные
4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1
Выходные данные
1
0
0