D. Забор
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Джона Доу есть кривой забор, состоящий из n прямоугольных досок выстроенных в ряд слева направо: i-тая (1 ≤ i ≤ n) по порядку (слева направо) доска имеет ширину 1 и высоту hi. Будем считать, что i-тая (1 ≤ i ≤ n) по порядку (слева направо) доска имеет номер i.

Кусок забора от l до r (1 ≤ l ≤ r ≤ n) — это последовательность досок с номерами от l до r включительно, то есть, доски с номерами l, l + 1, ..., r. Шириной куска забора от l до r называется величина r - l + 1.

Два куска забора от l1 до r1 и от l2 до r2 называются подходящими, если выполняются следующие условия:

  • куски не пересекаются, то есть, нет ни одной доски, такой, что она содержится в обоих кусках забора;
  • куски имеют одинаковую ширину;
  • для любого i (0 ≤ i ≤ r1 - l1) выполняется hl1 + i + hl2 + i = hl1 + hl2.

Джон выбрал несколько кусков забора и теперь хочет знать, сколько различных подходящих кусков существует для каждого из них. Два куска забора считаются различными, если существует такая доска, которая принадлежит одному из них и не принадлежит другому.

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

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество досок в заборе. Во второй строке через пробел записаны n целых чисел h1, h2, ..., hn (1 ≤ hi ≤ 109) — высоты досок забора.

В третьей строке записано целое число q (1 ≤ q ≤ 105) — количество запросов. В следующих q строках через пробел записаны два целых числа li и ri (1 ≤ li ≤ ri ≤ n) — границы i-го куска забора.

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

Для каждого запроса в отдельной строке выведите целое число — количество кусков забора, подходящих данному. Ответы для запросов выводите в том порядке, в котором запросы заданы во входных данных.

Примеры
Входные данные
10
1 2 2 1 100 99 99 100 100 100
6
1 4
1 2
3 4
1 5
9 10
10 10
Выходные данные
1
2
2
0
2
9