stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef long double ld;

typedef vector<vector<int>> Graph;

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};

#define pi 3.14159265359

#define inf 2147483647

#define INF 9223372036854775807

#define mod 1000000007

#define mod2 998244353



ll f(ll n, ll m) {

	return (n * n) % m;

}



int main() {

	ll N, X, M; cin >> N >> X >> M;

	ll A, preA, ans = 0;

	ll loopcnt = 0, cnt = 0, sum_loop = 0, rec_A;

	vector<int> visit(1000000);

	bool dub = false;

	for(int i = 1; i <= N; i++) {

		if(i == 1) {

			A = X;

			ans += A;

			visit[A] = 1;

			cnt++;

			continue;

		}

		preA = A;

		A = f(A, M);

		if(dub) {

			if(A == rec_A) break;

			ans += A; sum_loop += A; loopcnt++; cnt++;

		}

		else {

			if(visit[A]) {

				dub = true; rec_A = A; sum_loop += A; loopcnt++;

			}

			ans += A;

			cnt++;

			visit[A] = 1;

		}

	}

	A = preA;

	if(dub) {

		ans += sum_loop * ((N - cnt) / loopcnt);

		ll rem = (N - cnt) % loopcnt;

		for(int i = 0; i < rem; i++) {

			A = f(A, M);

			ans += A;

		}

	}

	cout << ans << endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.022251485572655x):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef long double ld;

typedef vector<vector<int>> Graph;

const int dx[4] = {1, 0, -1, 0};

const int dy[4] = {0, 1, 0, -1};

#define pi 3.14159265359

#define inf 2147483647

#define INF 9223372036854775807

#define mod 1000000007

#define mod2 998244353



ll f(ll n, ll m) {

	return (n * n) % m;

}



int main() {

	ll N, X, M; cin >> N >> X >> M;

	ll A, preA, ans = 0;

	ll loopcnt = 0, cnt = 0, sum_loop = 0, rec_A;

	vector<bool> visit(100001);

	bool dub = false;

	for(int i = 1; i <= N; i++) {

		if(i == 1) {

			A = X;

			ans += A;

			visit[A] = true;

			cnt++;

			continue;

		}

		preA = A;

		A = f(A, M);

		if(dub) {

			if(A == rec_A) break;

			ans += A; sum_loop += A; loopcnt++; cnt++;

		}

		else {

			if(visit[A]) {

				dub = true; rec_A = A; sum_loop += A; loopcnt++;

			}

			ans += A;

			cnt++;

			visit[A] = true;

		}

	}

	A = preA;

	if(dub) {

		ans += sum_loop * ((N - cnt) / loopcnt);

		ll rem = (N - cnt) % loopcnt;

		for(int i = 0; i < rem; i++) {

			A = f(A, M);

			ans += A;

		}

	}

	cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<vector<ll>> dub(m, vector<ll>(40, -1));

    vector<vector<ll>> dubsum(m, vector<ll>(40, 0));

    rep(i, m){

        dub[i][0] = i*i%m;

    }

    rep(i, 39){

        rep(j,m){

            dub[j][i + 1] = dub[dub[j][i]][i];

        }

    }

    rep(i,m){

        dubsum[i][0] = i;

    }

    rep(i,39){

        rep(j,m){

            dubsum[j][i+1] = dubsum[j][i] + dubsum[dub[j][i]][i];

        }

    }

    ll ans = 0;

    ll bit = 0;

    ll now = x;

    while(n){

        if(n & 1){

            ans += dubsum[now][bit];

            now = dub[now][bit];

        }

        ++bit;

        n >>= 1;

    }

    cout << ans << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.786682891142507x):
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<ll> spare(m, -1);

    ll now = x;

    if(n <= 1e8){

        ll ans = 0;

        ll now = x;

        rep(i,n){

            ans += now;

            now = now*now%m;

        }

        cout << ans << endl;

        return 0;

    }

    rep(i,m){

        if(spare[now] != -1) break;

        else{

            spare[now] = i;

            now = now*now%m; 

        }

    }

    ll start = spare[now];

    ll end = i;

    ll shuuki = end-start;

    now = x;

    ll ans = 0;

    for(i = 0;i < start;++i){

        ans += now;

        now = now*now%m;

        --n;

        if(n == 0){

            cout << ans << endl;

        }

    }

    ll kurikaesi = 0;

    for(i = start;i < end;++i){

        kurikaesi += now;

        now = now*now % m;

    }

    ans += n/shuuki*kurikaesi;

    n %= shuuki;

    while(n){

        ans += now;

        now = now*now%m;

        --n;

    }

    cout << ans << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<vector<int>> dub(m, vector<int>(40, -1));

    vector<vector<ll>> dubsum(m, vector<ll>(40, 0));

    rep(i, m){

        dub[i][0] = i*i%m;

    }

    rep(i, 39){

        rep(j,m){

            dub[j][i + 1] = dub[dub[j][i]][i];

        }

    }

    rep(i,m){

        dubsum[i][0] = i;

    }

    rep(i,39){

        rep(j,m){

            dubsum[j][i+1] = dubsum[j][i] + dubsum[dub[j][i]][i];

        }

    }

    ll ans = 0;

    int bit = 0;

    int now = x;

    while(n){

        if(n & 1){

            ans += dubsum[now][bit];

            now = dub[now][bit];

        }

        ++bit;

        n >>= 1;

    }

    cout << ans << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.0157907420285464x):
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<ll> spare(m, -1);

    ll now = x;

    if(n <= 1e8){

        ll ans = 0;

        ll now = x;

        rep(i,n){

            ans += now;

            now = now*now%m;

        }

        cout << ans << endl;

        return 0;

    }

    rep(i,m){

        if(spare[now] != -1) break;

        else{

            spare[now] = i;

            now = now*now%m; 

        }

    }

    ll start = spare[now];

    ll end = i;

    ll shuuki = end-start;

    now = x;

    ll ans = 0;

    for(i = 0;i < start;++i){

        ans += now;

        now = now*now%m;

        --n;

        if(n == 0){

            cout << ans << endl;

        }

    }

    ll kurikaesi = 0;

    for(i = start;i < end;++i){

        kurikaesi += now;

        now = now*now % m;

    }

    ans += n/shuuki*kurikaesi;

    n %= shuuki;

    while(n){

        ans += now;

        now = now*now%m;

        --n;

    }

    cout << ans << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<vector<ll>> dub(m, vector<ll>(40, -1));

    vector<vector<ll>> dubsum(m, vector<ll>(40, 0));

    rep(i, m){

        dub[i][0] = i*i%m;

    }

    rep(i, 39){

        rep(j,m){

            dub[j][i + 1] = dub[dub[j][i]][i];

        }

    }

    rep(i,m){

        dubsum[i][0] = i;

    }

    rep(i,39){

        rep(j,m){

            dubsum[j][i+1] = dubsum[j][i] + dubsum[dub[j][i]][i];

        }

    }

    ll ans = 0;

    ll bit = 0;

    ll now = x;

    while(n){

        if(n & 1){

            ans += dubsum[now][bit];

            now = dub[now][bit];

        }

        ++bit;

        n >>= 1;

    }

    cout << ans << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.790036986840397x):
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<ll> spare(m, -1);

    ll now = x;

    /**

    if(n <= 1e7){

        ll ans = 0;

        ll now = x;

        rep(i,n){

            ans += now;

            now = now*now%m;

        }

        cout << ans << endl;

        return 0;

    }**/

    rep(i,m){

        if(spare[now] != -1) break;

        else{

            spare[now] = i;

            now = now*now%m; 

        }

    }

    ll start = spare[now];

    ll end = i;

    ll shuuki = end-start;

    now = x;

    ll ans = 0;

    for(i = 0;i < start;++i){

        ans += now;

        now = now*now%m;

        --n;

        if(n == 0){

            cout << ans << endl;

            return 0;

        }

    }

    ll kurikaesi = 0;

    for(i = start;i < end;++i){

        kurikaesi += now;

        now = now*now % m;

    }

    ans += n/shuuki*kurikaesi;

    n %= shuuki;

    while(n){

        ans += now;

        now = now*now%m;

        --n;

    }

    cout << ans << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<vector<int>> dub(m, vector<int>(40, -1));

    vector<vector<ll>> dubsum(m, vector<ll>(40, 0));

    rep(i, m){

        dub[i][0] = i*i%m;

    }

    rep(i, 39){

        rep(j,m){

            dub[j][i + 1] = dub[dub[j][i]][i];

        }

    }

    rep(i,m){

        dubsum[i][0] = i;

    }

    rep(i,39){

        rep(j,m){

            dubsum[j][i+1] = dubsum[j][i] + dubsum[dub[j][i]][i];

        }

    }

    ll ans = 0;

    int bit = 0;

    int now = x;

    while(n){

        if(n & 1){

            ans += dubsum[now][bit];

            now = dub[now][bit];

        }

        ++bit;

        n >>= 1;

    }

    cout << ans << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.0216650858935947x):
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<ll> spare(m, -1);

    ll now = x;

    /**

    if(n <= 1e7){

        ll ans = 0;

        ll now = x;

        rep(i,n){

            ans += now;

            now = now*now%m;

        }

        cout << ans << endl;

        return 0;

    }**/

    rep(i,m){

        if(spare[now] != -1) break;

        else{

            spare[now] = i;

            now = now*now%m; 

        }

    }

    ll start = spare[now];

    ll end = i;

    ll shuuki = end-start;

    now = x;

    ll ans = 0;

    for(i = 0;i < start;++i){

        ans += now;

        now = now*now%m;

        --n;

        if(n == 0){

            cout << ans << endl;

            return 0;

        }

    }

    ll kurikaesi = 0;

    for(i = start;i < end;++i){

        kurikaesi += now;

        now = now*now % m;

    }

    ans += n/shuuki*kurikaesi;

    n %= shuuki;

    while(n){

        ans += now;

        now = now*now%m;

        --n;

    }

    cout << ans << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<vector<ll>> dub(m, vector<ll>(40, -1));

    vector<vector<ll>> dubsum(m, vector<ll>(40, 0));

    rep(i, m){

        dub[i][0] = i*i%m;

    }

    rep(i, 39){

        rep(j,m){

            dub[j][i + 1] = dub[dub[j][i]][i];

        }

    }

    rep(i,m){

        dubsum[i][0] = i;

    }

    rep(i,39){

        rep(j,m){

            dubsum[j][i+1] = dubsum[j][i] + dubsum[dub[j][i]][i];

        }

    }

    ll ans = 0;

    ll bit = 0;

    ll now = x;

    while(n){

        if(n & 1){

            ans += dubsum[now][bit];

            now = dub[now][bit];

        }

        ++bit;

        n >>= 1;

    }

    cout << ans << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.790036986840397x):
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<ll> spare(m, -1);

    ll now = x;

    rep(i,m){

        if(spare[now] != -1) break;

        else{

            spare[now] = i;

            now = now*now%m; 

        }

    }

    ll start = spare[now];

    ll end = i;

    ll shuuki = end-start;

    now = x;

    ll ans = 0;

    for(i = 0;i < start;++i){

        ans += now;

        now = now*now%m;

        --n;

        if(n == 0){

            cout << ans << endl;

            return 0;

        }

    }

    ll kurikaesi = 0;

    for(i = start;i < end;++i){

        kurikaesi += now;

        now = now*now % m;

    }

    ans += n/shuuki*kurikaesi;

    n %= shuuki;

    while(n){

        ans += now;

        now = now*now%m;

        --n;

    }

    cout << ans << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<vector<int>> dub(m, vector<int>(40, -1));

    vector<vector<ll>> dubsum(m, vector<ll>(40, 0));

    rep(i, m){

        dub[i][0] = i*i%m;

    }

    rep(i, 39){

        rep(j,m){

            dub[j][i + 1] = dub[dub[j][i]][i];

        }

    }

    rep(i,m){

        dubsum[i][0] = i;

    }

    rep(i,39){

        rep(j,m){

            dubsum[j][i+1] = dubsum[j][i] + dubsum[dub[j][i]][i];

        }

    }

    ll ans = 0;

    int bit = 0;

    int now = x;

    while(n){

        if(n & 1){

            ans += dubsum[now][bit];

            now = dub[now][bit];

        }

        ++bit;

        n >>= 1;

    }

    cout << ans << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.0216650858935947x):
#include <bits/stdc++.h>

using namespace std;



#define rep(i,n) for(i = 0;i < n;++i)

#define all(v) v.begin(), v.end()

using ll = long long;



int main()

{

    ll i,j;

    ll n,x,m;

    cin >> n >> x >> m;

    vector<ll> spare(m, -1);

    ll now = x;

    rep(i,m){

        if(spare[now] != -1) break;

        else{

            spare[now] = i;

            now = now*now%m; 

        }

    }

    ll start = spare[now];

    ll end = i;

    ll shuuki = end-start;

    now = x;

    ll ans = 0;

    for(i = 0;i < start;++i){

        ans += now;

        now = now*now%m;

        --n;

        if(n == 0){

            cout << ans << endl;

            return 0;

        }

    }

    ll kurikaesi = 0;

    for(i = start;i < end;++i){

        kurikaesi += now;

        now = now*now % m;

    }

    ans += n/shuuki*kurikaesi;

    n %= shuuki;

    while(n){

        ans += now;

        now = now*now%m;

        --n;

    }

    cout << ans << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

// #include <atcoder/all>

using namespace std;

// using namespace atcoder;

using ll = long long;

using ull = unsigned long long;

#define REP(i,n) for (ll i = 0; i < (n); ++i)

#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)

#define ALL(v) (v).begin(), (v).end()

template<class T>

using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;





int main(){

    ll n, x, m;

    cin >> n >> x >> m;



    vector<vector<ll>> nxt(40, vector<ll>(m, 0));

    vector<vector<ll>> s(40, vector<ll>(m, 0));

    REP(y, m){

        nxt.at(0).at(y) = (y * y) % m;

        s.at(0).at(y) = y;

    }



    for(ll i = 1; i < 40; ++i){

        REP(y, m){

            const ll n1 = nxt.at(i - 1).at(y);

            s.at(i).at(y) = s.at(i - 1).at(n1) + s.at(i - 1).at(y);

            nxt.at(i).at(y) = nxt.at(i - 1).at(n1);

        }

    }



    ll ans = 0;

    for(ll i = 0; i < 40; ++i){

        if((n >> i) & 1){

            ans += s.at(i).at(x);

            x = nxt.at(i).at(x);

        }

    }

    cout << ans << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.4101416830163844x):
#include <bits/stdc++.h>

// #include <atcoder/all>

using namespace std;

// using namespace atcoder;

using ll = long long;

using ull = unsigned long long;

#define REP(i,n) for (ll i = 0; i < (n); ++i)

#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)

#define ALL(v) (v).begin(), (v).end()

template<class T>

using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;





template<typename S, S op(S, S)>

struct Doubling {

    vector<vector<S>> v;



    Doubling(const vector<S>& step1, ll p){

        const auto n = step1.size();

        v.resize(p);

        v.at(0) = step1;

        for(ll i = 1; i < p; ++i){

            v.at(i).resize(n);

            for(ll j = 0; j < n; ++j){

                const auto& x = v.at(i - 1).at(j);

                const auto& y = v.at(i - 1).at(x.index);

                v.at(i).at(j) = op(x, y);

            }

        }

    }



    S query(S init, ll nstep){

        S ret = init;

        REP(i, v.size()){

            if((nstep >> i) & 1){

                ret = op(ret, v.at(i).at(ret.index));

            }

        }

        return ret;

    }

};



struct S{ ll sum, index; };

S op(S x, S y){ return S{x.sum + y.sum, y.index }; }



int main(){

    ll n, x, m;

    cin >> n >> x >> m;



    vector<S> step1(m);

    REP(i, m){

        step1.at(i) = {i, (i * i) % m};

    }



    Doubling<S, op> dbl(step1, 40);



    const auto ans = dbl.query(S{0, x}, n);

    cout << ans.sum << endl;



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define P pair<ll,ll>

#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)

#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)

#define TO(x,t,f) ((x)?(t):(f))

#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9

#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted

#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted

#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted

#define REV(x) (reverse(x.begin(),x.end())) //reverse

ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}

ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*b);}

#define NEXTP(x) next_permutation(x.begin(),x.end())

const ll INF=ll(1e16)+ll(7);

const ll MOD=1000000007LL;

#define out(a) cout<<fixed<<setprecision((a))

//tie(a,b,c) = make_tuple(10,9,87);

#define pop_(a) __builtin_popcount((a))

ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}







int main(){

	ll N,X,M;

	cin >> N >> X >> M;



	//今iにいて2^j個先に行ったとき



	ll pla[M][35]={},bal[M][35]={};



	FOR(i,0,M){

		pla[i][0] = i*i % M;

		bal[i][0] = i*i % M;

	}

	FOR(j,1,35)FOR(i,0,M){

		pla[i][j] = pla[ pla[i][j-1] ][j-1];

		bal[i][j] = bal[i][j-1] + bal[ pla[i][j-1] ][j-1];

	}



	ll ans = X;

	N--;

	FOR(i,0,35){

		if(N&(1LL<<i)){

			ans += bal[X][i];

			X = pla[X][i];

		}

	}

	cout << ans << endl;



}


// Faster C++ solution for the same problem (measured speedup: 1.8316200750263867x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define P pair<ll,ll>

#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)

#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)

#define TO(x,t,f) ((x)?(t):(f))

#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9

#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted

#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted

#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted

#define REV(x) (reverse(x.begin(),x.end())) //reverse

ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}

ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*b);}

#define NEXTP(x) next_permutation(x.begin(),x.end())

const ll INF=ll(1e16)+ll(7);

const ll MOD=1000000007LL;

#define out(a) cout<<fixed<<setprecision((a))

//tie(a,b,c) = make_tuple(10,9,87);

#define pop_(a) __builtin_popcount((a))

ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}







int main(){

	ll N,X,M;

	cin >> N >> X >> M;

	ll ans = 0;



	vector<ll> did(M+9,0),sum(M+9,0);

	ll b = M;



	while(N>0){

		if(did[X]){

			ll loop_point = sum[b] - sum[X] + X;

			if(b==X){

				ans += X*N;

				cout << ans << endl;

				return 0;

			}

			ans += loop_point * ( N / (did[b]-did[X]+1) );

			N %= (did[b]-did[X]+1);

		}



		if(N>0){

			did[X] = did[b] + 1;

			N--;

			ans += X;

			sum[X] = sum[b] + X;

			b = X;

			X = X*X%M;

		}



		if(X==0)break;



	}





	cout << ans << endl;



}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ALL(x) x.begin(),x.end()

#define rep(i,n) for(int i=0;i<n;i++)

#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 

#define INF 1000000000

#define mod 1000000007

typedef long long ll;

const ll LINF = 1001002003004005006ll;

int dx[]={1,0,-1,0};

int dy[]={0,1,0,-1};

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



signed main(){

    cin.tie(0);

    ios::sync_with_stdio(0);



    int n,k;cin>>n>>k;

    vector<ll> h(n+1);

    rep(i,n) cin>>h[i+1];



    //まず，ある列を操作すること，その列を完全に消すことは同値(これは自分で気づけた)

    //消す列を選ぶ

    //うまくDPするために

    //必要な情報はDPのindex(次元？)に持たせる

    //何回操作したかとか，あと何回操作したかとかをDPに持たせるのはとても自然な考えだけど，もう一つ

    //今回，ある状況での部分解は削除しなかった最後の列に依るんだからそこを持ったほうがいいとわかる

    //なるほどなぁ

    ll dp[310][310];

    rep(i,310)rep(j,310) dp[i][j]=LINF;

    dp[0][0]=0;

    // dp[i][j] : 最後にi列を使った，サイズがj

    // dp[i][j]=min(k=1 to i-1  dp[k][j-1]+max(0,h[i]-h[k]))



    for(int j=1;j<=n-k;j++){

        for(int i=1;i<=n;i++){

            for(int k=0;k<i;k++){

                chmin(dp[i][j],dp[k][j-1]+max(0ll,h[i]-h[k]));

            }

        }

    }

    ll ans=LINF;

    rep(i,n+1){

        chmin(ans,dp[i][n-k]);

    }

    cout<<ans<<endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7694755565726275x):
#include<bits/stdc++.h>

using namespace std;

#define ALL(x) x.begin(),x.end()

#define rep(i,n) for(int i=0;i<n;i++)

#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 

#define INF 1000000000

#define mod 1000000007

using ll=long long;

const ll LINF = 1001002003004005006ll;

int dx[]={1,0,-1,0};

int dy[]={0,1,0,-1};

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int n,k;

vector<ll> h;



inline ll cost(int a,int b){

    return (max(0ll,h[b]-h[a]));

}



signed main(){

    cin.tie(0);

    ios::sync_with_stdio(0);

    

    cin>>n>>k;

    h.resize(n+1);

    rep(i,n) cin>>h[i+1];

    h[0]=0;



    if(k>=n){

        cout<<0<<endl;

        return 0;

    }



    ll dp[n+1][k+1];

    rep(i,n+1){

        rep(j,k+1){

            dp[i][j]=INF*100ll;

        }

    }

    dp[0][0]=0;



    rep(j,k+1){

        rep(i,n){

            for(int l=0;l<=k and j-l>=0 and i-l>=0;l++){

                chmin(dp[i+1][j],dp[i-l][j-l]+cost(i-l,i+1));

            }

        }

    }

    // rep(j,k+1){

    //     rep(i,n+1){

    //         cout<<dp[i][j]<<"  ";

    //     }cout<<endl;

    // }

    ll ans=LINF;

    rep(i,k+1){

        chmin(ans,dp[n-i][k-i]);

    }

    cout<<ans<<endl;

    return 0;

}