408275: GYM103075 H Рудольф и гидродинамика

H. Рудольф и гидродинамикаограничение по времени на тест2 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

Рудольф пишет диссертацию, посвящённую физике течения жидкости. Для экспериментов Рудольф соорудил необычную лабораторную установку, представляющую собой... аквариум.

Внутри аквариума есть $$$N$$$ поперечных перегородок, расположенных на равных расстояниях друг от друга и от стенок аквариума. Перегородки пронумерованы слева направо числами от $$$0$$$ до $$$(N - 1)$$$; высота $$$i$$$-й перегородки равна $$$H_i$$$. Высота боковых стенок аквариума очень велика; фактически, её можно считать неограниченной.

Пространство, ограниченное соседними перегородками или боковыми стенками аквариума, будем называть сектором. Нетрудно видеть, что аквариум оказывается разделён на $$$(N + 1)$$$ секторов. Секторы нумеруются слева направо числами от $$$0$$$ до $$$N$$$.

Изначально аквариум не содержит воды.

В рамках своих экспериментов Рудольф выполняет два вида действий: либо доливает некоторый объём воды в определённый сектор, либо измеряет высоту столба воды в определённом секторе.

При увеличении объёма воды в секторе на 1 высота столба воды увеличивается также на 1. Если высота столба воды превышает высоту левой или правой перегородки, то вода переливается в соседние секторы (которые также могут переполниться, и тогда вода распространяется дальше).

Помогите Рудольфу проконтролировать правильность его измерений.

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

Первая строка содержит целое число $$$N$$$ ($$$0 \le N \le 1000$$$) — количество перегородок.

Вторая строка содержит $$$N$$$ целых чисел $$$H_i$$$ ($$$0 \le H_i \le 10^9$$$) — высоту каждой из перегородок.

Третья строка содержит целое число $$$Q$$$ ($$$1 \le Q \le 10^5$$$) — количество действий Рудольфа.

Следующие $$$Q$$$ строк описывают действия Рудольфа. Каждая из них содержит целое число $$$T_j$$$ ($$$T_j \in \left\{1, 2\right\}$$$) — вид действия. Если $$$T_j = 1$$$, то далее следуют целые числа $$$S_j$$$ и $$$V_j$$$ ($$$0 \le S_j \le N$$$, $$$1 \le V_j \le 10^9$$$) — соответственно номер сектора, в который Рудольф наливает воду, и объём воды. Если $$$T_j = 2$$$, то далее следует целое число $$$S_j$$$ ($$$0 \le S_j \le N$$$) — номер сектора, в котором Рудольф проверяет уровень воды.

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

Для каждого действия вида 2 выведите вещественное число — высоту столба воды в интересующем секторе. Абсолютная или относительная погрешность ответа не должна превышать $$$10^{-6}$$$.

ПримерыВходные данные

3
3 2 2
6
1 0 2
1 3 3
2 0
2 1
2 2
2 3

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

2.00000000
0.00000000
1.00000000
2.00000000

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

2
3 3
4
1 1 4
2 0
2 1
2 2

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

0.50000000
3.00000000
0.50000000