using namespace std;
const int NMAX = 1e5 + 11;
int n, k, h[NMAX], mem[NMAX];
bool vis[NMAX];
inline int dh(int i, int j) { return (int)abs(h[i] - h[j]); }
int dp(int i)
{
    int &ans = mem[i];
    if (i == n - 1)
        return 0;
    if (vis[i])
        return ans;
    vis[i] = true;
    ans = INT_MAX;
    for (int j = i + 1; j <= i + k; ++j)
        if (j < n)
            ans = min(ans, dp(j) + dh(i, j));
    return ans;
}
int main(void)
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> h[i];
    cout << dp(0) << endl;
    return 0;
}

using namespace std;
const int NMAX = 1e5 + 11;
int n, h[NMAX], mem[NMAX];
bool vis[NMAX];
inline int dh(int i, int j) { return (int)abs(h[i] - h[j]); }
int dp(int i)
{
    int &ans = mem[i];
    if (i == n - 1)
        return 0;
    if (vis[i])
        return ans;
    vis[i] = true;
    ans = dp(i + 1) + dh(i, i + 1);
    if (i + 2 < n)
        ans = min(ans, dp(i + 2) + dh(i, i + 2));
    return ans;
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> h[i];
    cout << dp(0) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int solve(int n, string s)
{
    map<char, vi> pm = {
        {'A', vi(n, 0)}, {'T', vi(n, 0)}, {'C', vi(n, 0)}, {'G', vi(n, 0)}};
    string opts = "AGCT";
    for (int i = 0; i < n; ++i)
    {
        for (auto c : opts)
        {
            pm[c][i] += s[i] == c;
            if (i != 0)
                pm[c][i] += pm[c][i - 1];
        }
    }
    auto sum = [&pm](int l, int r, char c) {
        return pm[c][r] - (l > 0 ? pm[c][l - 1] : 0);
    };
    int ans = 0;
    for (int l = 0; l < n - 1; ++l)
    {
        for (int r = l + 1; r < n; ++r)
        {
            ans += (sum(l, r, 'A') == sum(l, r, 'T') and
                    sum(l, r, 'C') == sum(l, r, 'G'));
        }
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    string s;
    cin >> n >> s;
    cout << solve(n, s) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    int x = (a + b) / 2;
    int y = (a - b) / 2;
    cout << x << " " << y << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const NMAX = 1e5 + 11;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi f0(NMAX, 0), f1(NMAX, 0), f2(NMAX, 0);
    for (int i = 0; i < n; ++i)
    {
        int ai;
        cin >> ai;
        if (i % 2 == 0)
            ++f0[ai];
        else
            ++f1[ai];
        ++f2[ai];
    }
    sort(f0.begin(), f0.end(), greater<int>());
    sort(f1.begin(), f1.end(), greater<int>());
    sort(f2.begin(), f2.end(), greater<int>());
    f0;
    if (f2[0] == f0[0] + f1[0])
        cout << n - max(f0[0] + f1[1], f0[1] + f1[0]) << endl;
    else
        cout << n - f0[0] - f1[0] << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    read_n(a.begin(), n);
    sort(a.begin(), a.end());
    int ai = a.back();
    int aj = *max_element(a.begin(), prev(a.end()), [ai](int x, int y) {
        return min(x, ai - x) < min(y, ai - y);
    });
    cout << ai << " " << aj << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const NMAX = 2e5 + 11;
int n, m, d[NMAX], ans[NMAX], vis[NMAX];
vector<ii> g[NMAX];
ii edges[NMAX];
void dfs(int u)
{
    vis[u] = true;
    for (auto [v, w] : g[u])
    {
        if (vis[v])
            continue;
        ans[v] = ans[u] + w;
        dfs(v);
    }
}
bool solve(void)
{
    for (int u = 0; u < n; u++)
        if (not vis[u])
            dfs(u);
    for (int i = 0; i < m; i++)
    {
        auto [u, v] = edges[i];
        if (ans[v] - ans[u] != d[i])
            return false;
    }
    return true;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v >> d[i], u--, v--;
        edges[i] = {u, v};
        g[u].emplace_back(v, d[i]);
        g[v].emplace_back(u, -d[i]);
    }
    cout << (solve() ? "Yes" : "No") << endl;
    return 0;
}

using namespace std;
int n;
map<int, int> counter;
int main(void)
{
    int ai, ans = 0, num, times;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> ai;
        ++counter[ai];
    }
    for (auto num_times : counter)
    {
        num = num_times.first;
        times = num_times.second;
        if (num == times)
            continue;
        while (times != num and times != 0)
        {
            --times;
            ++ans;
        }
    }
    cout << ans << endl;
}

using namespace std;
using ll = long long;
int main(void)
{
    ios::sync_with_stdio(0), cin.tie(NULL);
    int n;
    string s;
    cin >> s;
    n = s.size() + 1;
    vector<ll> a(n, 0);
    for (int i = 0; i < n - 1; ++i)
        if (s[i] == '<')
            a[i + 1] = max(a[i + 1], a[i] + 1);
    for (int i = n - 2; i >= 0; --i)
        if (s[i] == '>')
            a[i] = max(a[i], a[i + 1] + 1);
    cout << accumulate(a.begin(), a.end(), (ll)0) << endl;
    return 0;
}

using namespace std;
using ll = long long;
int main(void)
{
    string s;
    int wcnt = 0;
    ll ans = 0;
    cin >> s;
    for (int i = (int)s.size() - 1; i >= 0; --i)
    {
        if (s[i] == 'W')
            ++wcnt;
        else
            ans += wcnt;
    }
    cout << ans << endl;
    return 0;
}