lli tre[maxn];
inline lli lowbit(lli x) { return x & -x; }
inline void upd(lli i, lli x) {
for (; i <= n; i += lowbit(i))
tre[i] += x;
}
inline lli ask(lli i) {
lli res = 0;
for (; i > 0; i -= lowbit(i))
res += tre[i];
return res;
}