#include #include #include #include #include #include #include #include using namespace std; typedef long long LL; #define sqr(x) ((x)*(x)) #define mp make_pair inline long long read(){ long long x = 0; char ch = getchar(); bool positive = 1; for (; !isdigit(ch); ch = getchar()) if (ch == '-') positive = 0; for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0'; return positive ? x : -x; } inline void write(long long a){ if(a>=10)write(a/10); putchar('0'+a%10); } inline void writeln(long long a){ if(a<0){ a=-a; putchar('-'); } write(a); puts(""); } const long long N=100005; long long n,q,tong[1000005],f[N],sum[N],a[N]; int main(){ cin>>n; cout<