#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; using ll = long long; using mint = modint1000000007; template struct BIT { vector bit; long long N; BIT (long long n){ N = n; bit.resize(N); } void add(long long loc, T val){ loc++; while(loc <= N){ bit[loc-1] += val; loc += loc & -loc; } } T sum(long long l, long long r){ T res = _sum(r) - _sum(l-1); return res; } T _sum(long long r){ r++; T res = 0; while(r > 0){ res += bit[r-1]; r -= r & -r; } return res; } }; template void compress(vector &A){ map comp; int N = A.size(), i=0; for (int i=0; i> N >> K; vector A(N); for (int i=0; i> A[i]; cin >> S; compress(A); vector> dp(K+1, BIT(N)); for (int i=0; i