Abc 371 D 1D Country

数轴上有 N 个村庄。第 i 个村庄位于坐标 X i 处，有 P i 个村民。

回答 Q 个查询。第 i 个查询的格式如下：

给定整数

L i 和 R i ，求出位于坐标 L i 和 R i 之间（含）村庄的村民总数。

约束条件

1≤N,Q≤2×10 5

−10 9 ≤X 1 <X2 <…<X N ≤109

1≤P i ≤10 9 −10 9 ≤Li ≤R i ≤10 9

所有输入值均为整数。

输入

输入来自标准输入，格式如下：

N

X 1 … X N

P1 … P N

Q

L1 R 1

⋮

L Q R Q

-----------

坐标轴有负数，所以直接用数组做前缀和就不行了，想了半个小时，想到了treemap，于是试着写一下，没想到居然写出来了。。。。