template<typename T>
struct Bit
{
T c[N];
void add(T x, const T v)
{
for (; x <= n; x += x & -x) c[x] += v;
}
T query(T x)
{
T res = 0;
for (; x; x -= x & -x) res += c[x];
return res;
}
} tr;