Educational Codeforces Round 131 (Rated for Div. 2)

#include <bits/stdc++.h>
using namespace std;
struct FAST_IO {
  FAST_IO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  }
} __fast_io;
#define cons(a, ...) a = typename decay<decltype(a)>::type(__VA_ARGS__)
using INT = int;
using f32 = float;
using f64 = double;
using f128 = long double;
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
using ll = long long;

template <class T1, class T2>
bool cmin(T1 &a, const T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <class T1, class T2>
bool cmax(T1 &a, const T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <class T1, class T2, class... T3>
bool cmin(T1 &a, const T2 b, const T3... rest) {
  return cmin(a, b) | cmin(a, rest...);
}
template <class T1, class T2, class... T3>
bool cmax(T1 &a, const T2 b, const T3... rest) {
  return cmax(a, b) | cmax(a, rest...);
}

bool MULTIDATA = true;

template <class T, size_t n>
struct arr;

template <class T, size_t n>
class tuple_size<arr<T, n>> {
 public:
  constexpr static size_t value = n;
};
template <class T>
struct arr_dtype {
  using type = T;
};
template <class T, size_t n>
struct arr_dtype<arr<T, n>> {
  using type = typename arr_dtype<T>::type;
};
template <class T, size_t n>
struct arr : public array<T, n> {
  using dvalue_type = typename arr_dtype<T>::type;
  using array<T, n>::array;
  template <class... Args>
  arr(T a, Args... args) : array<T, n>{a, args...} {}
  template <class U>
  arr(const arr<U, n> &a) {
    for (size_t i = 0; i < n; i++) (*this)[i] = a[i];
  }
#define TMP_ARR                              \
  template <class AT = void, class T2,       \
            class TU = typename conditional< \
                is_same<AT, void>::value,    \
                decltype(declval<T>() + declval<T2>()), AT>::type>
#define op_arr(x)                                            \
  TMP_ARR arr<T, n> &operator x##=(const arr<T2, n> &b) {    \
    for (size_t i = 0; i < n; i++) (*this)[i] x## = b[i];    \
    return *this;                                            \
  }                                                          \
  TMP_ARR arr<T, n> &operator x##=(const T2 &b) {            \
    for (size_t i = 0; i < n; i++) (*this)[i] x## = b;       \
    return *this;                                            \
  }                                                          \
  TMP_ARR arr<TU, n> operator x(const arr<T2, n> &b) const { \
    arr<TU, n> c = (*this);                                  \
    for (size_t i = 0; i < n; i++) c[i] x## = b[i];          \
    return c;                                                \
  }                                                          \
  TMP_ARR arr<TU, n> operator x(const T2 &b) const {         \
    arr<TU, n> c = (*this);                                  \
    for (size_t i = 0; i < n; i++) c[i] x## = b;             \
    return c;                                                \
  }
  op_arr(+) op_arr(-) op_arr(*) op_arr(/)
};
template <class T>
using arr2 = arr<T, 2>;
template <class T>
using arr3 = arr<T, 3>;
template <
    class AT = void, class T, size_t d,
    class UT = typename conditional<is_same<AT, void>::value, T, AT>::type>
UT dot(const arr<T, d> &a, const arr<T, d> &b) {
  UT c = 0;
  for (auto &i : operator*<UT>(a, b)) c += i;
  return c;
}
template <
    class AT = void, class T, size_t d,
    class UT = typename conditional<is_same<AT, void>::value, T, AT>::type>
UT _abs(const arr<T, d> &a) {
  return sqrt(dot<UT>(a, a));
}
template <
    class AT = void, class T, size_t d,
    class UT = typename conditional<is_same<AT, void>::value, T, AT>::type>
arr<UT, d> normalize(const arr<T, d> &a) {
  return a / _abs<UT>(a);
}
template <class T>
T crs(const arr2<T> &a, const arr2<T> &b) {
  return a[0] * b[1] - a[1] * b[0];
}
template <class T>
arr3<T> crs(const arr3<T> &a, const arr3<T> &b) {
  return {a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2],
          a[0] * b[1] - a[1] * b[0]};
}

template <class T, size_t n, size_t m>
struct mat : public array<arr<T, m>, n> {
  using array<arr<T, m>, n>::array;
  template <class... Args>
  mat(arr<T, m> a, Args... args) : array<arr<T, m>, n>{a, args...} {}
  template <class U>
  mat(const array<arr<U, m>, n> &a) {
    for (size_t i = 0; i < n; i++) (*this)[i] = a[i];
  }
  static mat<T, n, m> unit() {
    mat<T, n, m> a{};
    for (size_t i = 0; i < min(n, m); i++) a[i][i] = 1;
    return a;
  }
  static constexpr mat<T, n, m> zero() { return mat<T, n, m>{}; }
};
template <class T, size_t n, size_t m>
class tuple_size<mat<T, n, m>> {
 public:
  constexpr static size_t value = n;
};

template <class AT = void, class T, class U, size_t n, size_t m,
          class UT = typename conditional<is_same<AT, void>::value,
                                          decltype(declval<T>() * declval<U>()),
                                          AT>::type>
mat<UT, n, m> operator+(const mat<T, n, m> &a, const mat<U, n, m> &b) {
  mat<UT, n, m> x;
  for (size_t i = 0; i < n; i++) x[i] = a[i] + b[i];
  return x;
}

template <class AT = void, class T, class U, size_t n, size_t m,
          class UT = typename conditional<is_same<AT, void>::value,
                                          decltype(declval<T>() * declval<U>()),
                                          AT>::type>
mat<UT, n, m> operator-(const mat<T, n, m> &a, const mat<U, n, m> &b) {
  mat<UT, n, m> x;
  for (size_t i = 0; i < n; i++) x[i] = a[i] + b[i];
  return x;
}

template <class T, class U, size_t n, size_t m>
mat<T, n, m> &operator+=(mat<T, n, m> &a, const mat<U, n, m> &b) {
  for (size_t i = 0; i < n; i++) a[i] += b[i];
  return a;
}

template <class T, class U, size_t n, size_t m>
mat<T, n, m> &operator-=(mat<T, n, m> &a, const mat<U, n, m> &b) {
  for (size_t i = 0; i < n; i++) a[i] += b[i];
  return a;
}

template <class AT = void, class T, class U, size_t n, size_t m, size_t u,
          class UT = typename conditional<is_same<AT, void>::value,
                                          decltype(declval<T>() * declval<U>()),
                                          AT>::type>
mat<UT, n, u> operator*(const mat<T, n, m> &a, const mat<U, m, u> &b) {
  mat<UT, n, u> x{};
  for (size_t i = 0; i < n; i++)
    for (size_t j = 0; j < u; j++)
      for (size_t k = 0; k < m; k++) x[i][j] += a[i][k] * b[k][j];
  return x;
}

template <class AT = void, class T, class U, size_t n, size_t m, size_t u>
mat<T, n, u> &operator*=(mat<T, n, m> &a, const mat<U, m, u> &b) {
  return a = operator*<T>(a, b);
}

template <class T, class U, size_t n, size_t m>
mat<T, n, m> &operator*=(mat<T, n, m> &a, const U &b) {
  for (auto &i : a) i *= b;
  return a;
}

template <class T, class U, size_t n, size_t m>
mat<T, n, m> &operator/=(mat<T, n, m> &a, const U &b) {
  for (auto &i : a) i /= b;
  return a;
}

template <class T, class U, size_t n, size_t m>
mat<T, n, m> operator*(const mat<T, n, m> &a, const U &b) {
  mat<T, n, m> x;
  for (size_t i = 0; i < n; i++) x[i] = a[i] * b;
  return x;
}

template <class T, class U, size_t n, size_t m>
mat<T, n, m> operator/(mat<T, n, m> &a, const U &b) {
  mat<T, n, m> x;
  for (size_t i = 0; i < n; i++) x[i] = a[i] / b;
  return x;
}

template <
    class AT = void, class T, size_t n, size_t m,
    class UT = typename conditional<is_same<AT, void>::value, T, AT>::type>
pair<int, mat<UT, n, m>> inv(const mat<T, n, m> &_a) {
  mat<UT, n, m> a = _a;
  auto b = mat<UT, n, m>::unit();
  for (int i = 0; i < n - 1; i++) {
    int k = -1;
    for (int j = i; j < n; j++)
      if (a[j][i]) {
        k = j;
        break;
      }
    if (k != -1) {
      swap(a[i], a[k]);
      swap(b[i], b[k]);
      for (int j = i + 1; j < n; j++)
        if (a[k][i]) {
          UT d = a[j][i] / a[k][i];
          a[j] -= a[k] * d;
          b[j] -= b[k] * d;
        }
    }
  }
  int rank = 0;
  for (int i = n - 1; i >= 0; i--) {
    UT aii = a[i][i];
    if (aii) {
      rank++;
      b[i] /= aii;
      a[i] /= aii;
      for (int j = i - 1; j >= 0; j--) {
        UT aji = a[j][i];
        a[j] -= a[i] * aji;
        b[j] -= b[i] * aji;
      }
    }
  }
  return {rank, b};
}

template <
    class AT = void, class T, size_t n, size_t m,
    class UT = typename conditional<is_same<AT, void>::value, T, AT>::type>
UT det(const mat<T, n, m> &_a) {
  mat<UT, n, m> a = _a;
  vector<int> x(n, -1);
  int ans = 0, ii = 0;
  UT D = 1;
  for (int i = 0; i < n; i++) {
    int it = -1;
    for (int j = i; j < n; j++)
      if (a[j][ii]) {
        it = j;
        break;
      }
    if (it == -1) continue;
    swap(a[ii], a[it]);
    auto d = a[ii][x[ii] = i];
    a[ii] /= d;
    D *= d;
    for (int j = ii + 1; j < n; j++)
      if (a[j][i]) {
        UT d = a[j][i];
        a[j] -= a[ii] * d;
      }
    ans++;
    ii++;
  }
  return ans != n ? 0 : D;
}
constexpr unsigned long long operator"" _kb(unsigned long long i) {
  return i * 1024;
}
constexpr unsigned long long operator"" _mb(unsigned long long i) {
  return i * 1024_kb;
}
char pool[100_mb];
unsigned long long pooli = 0;
template <class T>
T *alloc(size_t i = 1) {
  auto pi = pooli;
  pooli += i * sizeof(T);
  return (T *)(void *)&pool[pi];
}
void reset() { pooli = 0; };
template <class T>
struct mallocator {
  typedef T value_type;
  mallocator() = default;
  template <class U>
  constexpr mallocator(const mallocator<U> &) noexcept {}
  [[nodiscard]] T *allocate(size_t n = 1) { return alloc<T>(n); }
  void deallocate(T *p, size_t n) noexcept {}
};

template <class T, class U>
bool operator==(const mallocator<T> &, const mallocator<U> &) {
  return true;
}
template <class T, class U>
bool operator!=(const mallocator<T> &, const mallocator<U> &) {
  return false;
}
template <class T, class... Args>
T *mnew(Args &&...args) {
  return ::new ((void *)(alloc<T>())) T(std::forward<Args>(args)...);
}
struct none_delete {
  constexpr none_delete() noexcept = default;
  template <class T>
  void operator()(T *p) const {};
};
template <template <class> class Allocator = allocator, class T>
T clone(const T &a) {
  return T(&(*(Allocator<typename pointer_traits<T>::element_type>().allocate(
                 1)) = *a));
}
template <class T, class IT = int>
struct segtree {
  const IT l, r;
  IT mid;
  T fmul, fsum;
  bool fable;
  segtree *ch[2];
  segtree(const int l, const int r)
      : l(l), r(r), mid(-1), fmul(T::unit()), fsum() {
    if (l != r) {
      mid = (l + r) / 2;
      ch[0] = mnew<segtree>(l, mid);
      ch[1] = mnew<segtree>(mid + 1, r);
      upload();
      fable = true;
    } else {
      fable = false;
      fsum = T{arr3<ll>{1, 0, 0}};
    }
  }
  void dmul(const T &v) {
    fmul *= v;
    fsum *= v;
  }
  void dable() { fable = !fable; }
  void download() {
    if (fmul != T::unit()) {
      ch[0]->dmul(fmul);
      ch[1]->dmul(fmul);
      fmul = T::unit();
    }
  }
  T sum_op() { return fable ? fsum : T(); }

  static T sum_merge1(T a) { return a; }

  static T sum_merge2(T a, T b) { return a + b; }
  static T sum_merge2(T a) { return a; }
  void upload() { fsum = sum_merge2(ch[0]->sum_op(), ch[1]->sum_op()); }
};
#define def_tree_edit(tag)                                                 \
  template <class T0, class... Args, class T3 = decltype(declval<T0>().l)> \
  void tag(T0 &tree, const T3 &L, const T3 &R, const Args &...v) {         \
    if (L <= tree.l && tree.r <= R) return tree.d##tag(v...);              \
    tree.download();                                                       \
    if (L <= tree.mid) tag(*tree.ch[0], L, R, v...);                       \
    if (tree.mid + 1 <= R) tag(*tree.ch[1], L, R, v...);                   \
    tree.upload();                                                         \
  }
#define def_tree_query(tag)                                               \
  template <class T0, class T3 = decltype(declval<T0>().l),               \
            class T2 =                                                    \
                typename decay<decltype(declval<T0>().tag##_op())>::type> \
  T2 tag(T0 &tree, const T3 &L, const T3 &R) {                            \
    if (L <= tree.l && tree.r <= R) return tree.tag##_op();               \
    tree.download();                                                      \
    bool l = L <= tree.mid, r = tree.mid + 1 <= R;                        \
    if (l && r)                                                           \
      return tree.tag##_merge2(tag(*tree.ch[0], L, R),                    \
                               tag(*tree.ch[1], L, R));                   \
    if (l) return tree.tag##_merge2(tag(*tree.ch[0], L, R));              \
    return tree.tag##_merge2(tag(*tree.ch[1], L, R));                     \
  }                                                                       \
  template <class T0, class T3 = decltype(declval<T0>().l),               \
            class T2 =                                                    \
                typename decay<decltype(declval<T0>().tag##_op())>::type> \
  T2 tag(T0 &tree, const T3 &LR) {                                        \
    if (LR == tree.l && tree.r == LR) return tree.tag##_op();             \
    tree.download();                                                      \
    if (LR <= tree.mid)                                                   \
      return tree.tag##_merge1(tag(*tree.ch[0], LR));                     \
    else                                                                  \
      return tree.tag##_merge1(tag(*tree.ch[1], LR));                     \
  }
def_tree_edit(mul) def_tree_edit(able) def_tree_query(sum) bool a[200001];
int main() {
  int q, d;
  cin >> q >> d;
  segtree<mat<ll, 3, 3>> t(0, 200000);
  mat<ll, 3, 3> D(arr3<ll>{1, 1, 1}, arr3<ll>{0, 1, 2}, arr3<ll>{0, 0, 1}),
      ID = inv<float>(D).second;
  while (q--) {
    int i;
    cin >> i;
    able(t, i, i);
    if (a[i] = !a[i]) {
      mul(t, max(0, i - d), i - 1, D);
    } else {
      mul(t, max(0, i - d), i - 1, ID);
    }
    cout << (t.fsum[0][2] - t.fsum[0][1]) / 2 << endl;
  }
}