Вам даны \(n\) точек на оси \(x\) с возрастающими целыми положительными координатами \(x_1 < x_2 < \ldots < x_n\).
Для каждой пары \((i, j)\), такой что \(1 \leq i < j \leq n\), строится отрезок \([x_i, x_j]\). Отрезки замкнуты, т.е. отрезок \([a, b]\) содержит точки \(a, a+1, \ldots, b\).
Вам даны \(q\) запросов. В \(i\)-м запросе задается целое положительное число \(k_i\), и нужно определить, сколько точек с целочисленными координатами содержится в ровно \(k_i\) отрезках.
Выходные данные
Для каждого набора входных данных выведите одну строку с \(q\) целыми числами, где \(i\)-е число является ответом на \(i\)-й запрос.
Примечание
В первом наборе входных данных построен только отрезок \([101, 200]\). Ни одна точка не содержится ровно в \(2\) отрезках, и \(100\) точек \(101, 102, \ldots, 200\) содержатся ровно в \(1\) отрезке.
Во втором примере построены \(15\) отрезков: \([1, 2], [1, 3], [1, 5], [1, 6], [1, 7], [2, 3], [2, 5], [2, 6], [2, 7], [3, 5], [3, 6], [3, 7], [5, 6], [5, 7], [6, 7]\). Точки \(1, 7\) содержатся в ровно \(5\) отрезках; точки \(2, 4, 6\) содержатся в ровно \(9\) отрезках; точки \(3, 5\) содержатся в ровно \(11\) отрезках.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2
101 200
2 1
6 15
1 2 3 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 8
254618033 265675151 461318786 557391198 848083778
6 9 15 10 6 9 4 4294967300
|
0 100
0 0 0 0 2 0 0 0 3 0 2 0 0 0 0
291716045 0 0 0 291716045 0 301749698 0
|