stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

char x[1000005];

int a=0,b=0,c=0,d=0,e,f,i,j,k,maxi=0;

int main(){

	fill(x,x+1000005,'A');

	scanf("%s",x);

int leng=strlen(x);

while(1){

if(a==leng){break;}

if(x[a]!='J'){

a++;

}else{

  while(1){

    if(x[a]=='J'){

      b++;

      a++;

    }else{

       break;

}}

while(1){

if(x[a]=='O'){

c++;

a++;

}else{

break;

}}

while(1){

if(x[a]=='I'){

d++;

a++;

}else{

break;

}}

if(b>=c && c<=d){

maxi=max(maxi,c);

}

b=0;

c=0;

d=0;

}

}

printf("%d\n",maxi);scanf("%d",&a);

return 0;

}

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

#include <string.h>

char s[1000005];

int min(int a,int b){ return a<b?a:b; }

int max(int a,int b){ return a>b?a:b; }

int main(){

	scanf("%s",&s); int n=strlen(s),beg=0,ret=0;

	while(beg<n)

	{

		if(s[beg]!='J') { beg++; continue; }

		int j=0,o=0,i=0;

		while(beg<n && s[beg]=='J'){ j++; beg++;}

		while(beg<n && s[beg]=='O'){ o++; beg++;}

		while(beg<n && s[beg]=='I'){ i++; beg++;}

		if(o==min(j,min(o,i)))

		{

			ret=max(ret,o);

		}

	}

	printf("%d\n",ret);

}
// Slower C++ solution:
//Bokan ga bokka--nn!!

//Daily Lunch Special Tanoshii !!

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <string>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

#include <functional>

#include <iostream>

#include <map>

#include <set>

using namespace std;

typedef pair<int,int> P;

typedef pair<int,P> P1;

typedef pair<P,P> P2;

typedef long long ll;

#define pu push

#define pb push_back

#define mp make_pair

#define eps 1e-7

#define INF 2000000000

#define s(x) scanf("%d",&x)

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

int main()

{

	string s;

	cin >> s;

	int id=0;

	int ret=0;

	while(id<s.size())

	{

		if(s[id]!='J')

		{

			id++;

			continue;

		}

		int j=0,o=0,i=0;

		while(id<s.size() && s[id]=='J') { j++; id++;}

		while(id<s.size() && s[id]=='O') { o++; id++;}

		while(id<s.size() && s[id]=='I') { i++; id++;}

		if(j<o || o>i) continue;

		ret=max(ret,o);

	}

	printf("%d\n",ret);

}

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

#include <string.h>

char s[1000005];

int min(int a,int b){ return a<b?a:b; }

int max(int a,int b){ return a>b?a:b; }

int main(){

	scanf("%s",&s); int n=strlen(s),beg=0,ret=0;

	while(beg<n)

	{

		if(s[beg]!='J') { beg++; continue; }

		int j=0,o=0,i=0;

		while(beg<n && s[beg]=='J'){ j++; beg++;}

		while(beg<n && s[beg]=='O'){ o++; beg++;}

		while(beg<n && s[beg]=='I'){ i++; beg++;}

		if(o==min(j,min(o,i)))

		{

			ret=max(ret,o);

		}

	}

	printf("%d\n",ret);

}
// Slower C++ solution:
#include <string>

#include <vector>

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

    string S; cin >> S;

    

    vector<char> v1;

    

    vector<int> v2; int c = 1;

    

    for(int i = 1; i < S.size(); i++)

    {

        if(S[i - 1] != S[i])

        {

            v1.push_back(S[i - 1]);

            v2.push_back(c);

            

            c = 0;

        }

        

        c++;

    }

    

    v1.push_back(S[S.size() - 1]);

    v2.push_back(c);

    

    int ret = 0;

    

    for(int i = 1; i < v1.size() -1; i++)

    {

        if(v1[i - 1] == 'J' && v1[i] == 'O' && v1[i + 1] == 'I' && v2[i - 1] >= v2[i] && v2[i] <= v2[i + 1])

        {

            ret = max(ret, v2[i]);

        }

    }

    

    printf("%d\n", ret);

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.272347368670193x):
#include <cstdio>

#include <cstring>

char s[1000009], t[1000009]; int c[1000009];

int main() {

	scanf("%s", s);

	int n = strlen(s);

	int p = 0, z = 0;

	for (int i = 1; s[i - 1]; i++) {

		if (s[i] != s[i - 1]) {

			t[z] = s[i - 1];

			c[z] = i - p;

			p = i; z++;

		}

	}

	int ret = 0;

	for (int i = 1; i < z - 1; i++) {

		if (t[i - 1] != 'J' || t[i] != 'O' || t[i + 1] != 'I') continue;

		if (c[i - 1] < c[i] || c[i] > c[i + 1]) continue;

		if (ret < c[i]) ret = c[i];

	}

	printf("%d\n", ret);

	return 0;

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

using namespace std;

 

typedef long double ld;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> i_i;

typedef pair<ll, int> ll_i;

typedef pair<int, ll> i_ll;

typedef pair<double, int> d_i;

typedef pair<ll, ll> ll_ll;

typedef pair<double, double> d_d;

struct edge { int u, v; ll w; };

 

ll MOD = 1000000007;

ll _MOD = 1000000009;

double EPS = 1e-10;

 

int main() {

	int N; cin >> N;

	string s; cin >> s;

	int M = s.length();

	vector<int> dp(N + 1);

	dp[0] = 1;

	for (int t = 0; t < N; t++) {

		vector<int> _dp(N + 1);

		for (int x = 0; x <= t; x++) {

			_dp[x + 1] = (_dp[x + 1] + dp[x]) % MOD;

			if (x) _dp[x - 1] = (_dp[x - 1] + dp[x] * 2LL) % MOD;

			else _dp[x] = (_dp[x] + dp[x]) % MOD;

		}

/*		cout << "at " << t+1 << " phase:\n";

		cout << "dp: ";

		for(int j = 0 ; j <= N ; j ++) cout << dp[j] << " ";cout << endl;

		cout << "_dp: ";

		for(int j = 0 ; j <= N ; j ++) cout << _dp[j] << " ";cout << endl;

*/		dp = _dp;

	}

	cout << dp[M] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.5669696760473402x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 5000

#define MO 1000000007

using namespace std;

char str[MAXN+5];

int N;

int dp[MAXN+5][MAXN+5];//dp[i][j]:走到第j位花了i步

int main()

{

	scanf("%d",&N);

	scanf("%s",str+1);

	int len=strlen(str+1);

//	int len=N/2;

	dp[0][0]=1;

	for(int tmn=1;tmn<=N;tmn++)

	{

		for(int pos=0;pos<=N;pos++)

		{

			if(pos!=N)

				dp[tmn][pos]=(1LL*dp[tmn][pos]+2LL*dp[tmn-1][pos+1]%MO)%MO;

			if(pos!=0)

				dp[tmn][pos]=(1LL*dp[tmn][pos]+1LL*dp[tmn-1][pos-1])%MO;

			if(pos==0)

				dp[tmn][pos]=(1LL*dp[tmn][pos]+1LL*dp[tmn-1][pos])%MO;

		}

	}

	printf("%d\n",dp[N][len]);

	return 0;

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

#define LL long long

#define Mod 1000000007

using namespace std;

int n,m;

int f[2][5005];

int main(){

	char*str=new char[5005];

	scanf("%d%s",&n,str);

	m=strlen(str);

	delete [] str;

	f[0][0]=1;

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

		int I=i&1;

		f[I][0]=(f[I^1][0]+f[I^1][1])%Mod;

		for(int j=1;j<=n;++j)

			f[I][j]=((LL)f[I^1][j-1]+f[I^1][j-1]+f[I^1][j+1])%Mod;

	}

	int Ans=f[n&1][m];

	for(int i=1;i<=m;++i) Ans=(LL)Ans*500000004%Mod;

	printf("%d",Ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2536534428860062x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 5000

#define MO 1000000007

using namespace std;

char str[MAXN+5];

int N;

int dp[MAXN+5][MAXN+5];//dp[i][j]:走到第i位花了j步

int main()

{

	scanf("%d",&N);

	scanf("%s",str+1);

	int len=strlen(str+1);

//	int len=N/2;

	dp[0][0]=1;

	for(int tmn=1;tmn<=N;tmn++)

	{

		for(int pos=0;pos<=N;pos++)

		{

			if(pos!=N)

				dp[tmn][pos]=(1LL*dp[tmn][pos]+2LL*dp[tmn-1][pos+1]%MO)%MO;

			if(pos!=0)

				dp[tmn][pos]=(1LL*dp[tmn][pos]+1LL*dp[tmn-1][pos-1])%MO;

			if(pos==0)

				dp[tmn][pos]=(1LL*dp[tmn][pos]+1LL*dp[tmn-1][pos])%MO;

		}

	}

	printf("%d\n",dp[N][len]);

	return 0;

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



#define int long long



using namespace std;



const int N = 5005;

const int mod = 1e9 + 7;



void add (int &x, int y) {

    x += y;

    x %= mod;

}



int dp[N], f[N];



signed main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);



    int n;

    string s;

    cin >> n >> s;



    dp[0] = 1;

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

        memset(f, 0, sizeof(f));

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

            add(f[j + 1], dp[j]);

            if (j) add(f[j - 1], 2 * dp[j]);

            else add(f[j], dp[j]);

        }



        for (int j = 0; j < N; j++) dp[j] = f[j];

    }



    cout << dp[s.length()];

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.425001575810751x):
#include<cstdio>

#include<cstring>

const long long mod=1e9+7;

long long matmod(long long val,long long k){

	long long ret=1ll;

	for(;k;k>>=1){

		if(k&1) ret=(val*ret)%mod;

		val=(val*val)%mod;

	}

	return ret;

}

void add(long long &des,long long sor){des+=sor;des%=mod;return ;}

char s[5005];

int n;

long long f[2][5005];

int main(){

	//freopen("keyboard.in","r",stdin);

	//freopen("keyboard.out","w",stdout);

	scanf("%d",&n);

	scanf("%s",s);

	int len=strlen(s);

	if(len>n){puts("0");return 0;}

	long long mul=matmod(2ll,len);

	f[0][0]=1ll;

	long long ans=f[0][len];

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

		f[i&1][0]=(f[(i-1)&1][0]+f[(i-1)&1][1])%mod;

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

			f[i&1][j]=0; 

			add(f[i&1][j],f[(i-1)&1][j-1]*2ll);

			add(f[i&1][j],f[(i-1)&1][j+1]);

		}

		add(ans,f[i&1][len]);

	}

	long long tmp=matmod(mul,mod-2ll);

	long long newans=f[n&1][len]*tmp%mod;

	printf("%lld\n",newans);

	return 0;

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



#define int long long



using namespace std;



const int N = 5005;

const int mod = 1e9 + 7;



void add (int &x, int y) {

    x += y;

    x %= mod;

}



int dp[N], f[N];



signed main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);



    int n;

    string s;

    cin >> n >> s;



    dp[0] = 1;

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

        memset(f, 0, sizeof(f));

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

            add(f[j + 1], dp[j]);

            if (j) add(f[j - 1], 2 * dp[j]);

            else add(f[j], dp[j]);

        }



        for (int j = 0; j < N; j++) dp[j] = f[j];

    }



    cout << dp[s.length()];

    return 0;

}


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



using namespace std;

#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)

#define REP(i,a,b) REPP(i,a,b,1)

#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)

#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) REP(i,0,(int)a-1)

#define FORD(i,a) REV(i,(int)a-1,0)

#define PB push_back

#define POB pop_back

#define MP make_pair

#define FI first

#define SE second

typedef long long ll;

typedef unsigned long long ull;

typedef pair < int , int > pii;

typedef vector < int > vi;

typedef vector < pii > vii;

typedef vector < ll > vl;



const double EPS = 1e-9;

const double PI = acos(-1);

const int INF = 1e9;

const ll MOD = 1e9 + 7;



ll addMod(ll a, ll b){

	return (a+b) % MOD;

}



ll mulMod(ll a, ll b){

	return (a*b) % MOD;

}



ll fast(ll a, ll b){

	if(b == 0) return 1;

	ll tmp = fast(a,b/2);

	tmp = mulMod(tmp, tmp);

	if(b % 2 == 1) tmp = mulMod(tmp,a);

	return tmp;

}



/////////////////////////////////////////////////////////



const int N = 5000;



ll dp[3][N + 5];

int n;

string str;



void precompute(){

	int bi = 0;

	dp[0][0] = 1;

	REP(use,1,n){

		REP(len,0,use){

			dp[1^bi][len] = dp[bi][len+1];

			if(len == 0) dp[1^bi][len] = addMod(dp[1^bi][len], dp[bi][0]);

			else dp[1^bi][len] = addMod(dp[1^bi][len], mulMod(2,dp[bi][len-1]));

		}

		bi ^= 1;

	}

}



ll solve(){

	precompute();

	return mulMod(dp[n%2][(int)str.length()], fast(fast(2, (int)str.length()), MOD-2));

}



int main(){

	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> str;

	cout << solve() << endl;

	return 0;

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

 

#define ll long long int

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define lim 200005

#define mod 1000000007

#define nfs_mw ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;



bool Q;

struct Line {

	mutable ll k, m, p;

	bool operator<(const Line& o) const {

		return Q ? p < o.p : k < o.k;

	}

};



//Line equation is k*x + m

//works for maximum, negate values for minimum

struct LineContainer : multiset<Line> {

	// (for doubles, use inf = 1/.0, div(a,b) = a/b)

	const ll inf = LLONG_MAX;

	ll div(ll a, ll b) { // floored division

		return a / b - ((a ^ b) < 0 && a % b); }

	bool isect(iterator x, iterator y) {

		if (y == end()) { x->p = inf; return false; }

		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;

		else x->p = div(y->m - x->m, x->k - y->k);

		return x->p >= y->p;

	}

	void add(ll k, ll m) {

		auto z = insert({k, m, 0}), y = z++, x = y;

		while (isect(y, z)) z = erase(z);

		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));

		while ((y = x) != begin() && (--x)->p >= y->p)

			isect(x, erase(y));

	}

	ll query(ll x) {

		assert(!empty());

		Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;

		return l.k * x + l.m;

	}

	void min_add(ll k, ll m) {

		add(-k, -m);

	}

	ll min_query(ll x) {

		return -query(x);

	}

};







int main()

{

    nfs_mw;

    int i,j,n; ll c, h, dp[lim] = {};

    cin>>n>>c;

    LineContainer idk;

    dp[0] = 0; cin>>h;

    idk.min_add(-2*h, dp[0] + h*h + c);

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

    	cin>>h;

    	dp[i] = idk.min_query(h) + h*h;

    	idk.min_add(-2*h, dp[i] + h*h + c);

    }

    cout<<dp[n-1];

}

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

#define ull uint64_t

#define ll long long int

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define mx5 100005

#define mx52 200005

#define mx6 1000005

#define mod 1000000007

#define nfs ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;



struct Line {

    ll m, c;

    double intersect(const Line& b) {

        return ((double)(c - b.c)) / (b.m - m);

    }



    ll eval(int x) {

        return m*x + c;

    }

};



Line getLine(ll dpi, ll hi) {

    return {-2*hi, hi*hi + dpi};

}



int main() {

    nfs

    int i, j, n;

    ll c, h[mx52];

    

    cin >> n >> c;

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

        cin >> h[i];

    }

    

    ll dp[n] = {};

    deque <Line> options(1, getLine(dp[0], h[0]));

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

        while (options.size() > 1 && options[0].intersect(options[1]) < h[i])

            options.pop_front();

        dp[i] = options[0].eval(h[i]) + h[i]*h[i] + c;

        Line newLine = getLine(dp[i], h[i]);

        int li = options.size() - 1;

        while (li and options[li].intersect(options[li - 1]) >= options[li].intersect(newLine)) {

            options.pop_back();

            li--;

        }

        options.push_back(newLine);

    }

    cout << dp[n - 1];

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdio>



using namespace std;



using ll = long long;

struct Line { ll a, b; ll get(ll x) { return a * x + b; } };



static const int MAX = 2e5 + 9;

const ll INFL = 1e17;



struct LiChaoTree

{

	int N;

    Line a[MAX << 2];

    ll h[MAX];



    void init (ll _h[MAX], int _N)

    {

    	N = _N;

    	copy (_h, _h + N, h);

    	for (int i = 0; i < (N << 2); ++i) a[i] = {0, INFL};

    }



    void upd (Line ln)

    {

        int root = 1, lo = 0, hi = N;

        while (true) {

			int mid = (lo + hi) >> 1;

            if (ln.get(h[mid]) < a[root].get(h[mid])) swap (ln, a[root]);

//            cerr << '[' << h[lo] << ", " << h[hi-1] << "]: " << a[root].a << ' ' << a[root].b << endl;

            if (lo + 1 >= hi) return;

            if (ln.get(h[lo]) < a[root].get(h[lo])) root = root << 1, hi = mid;

            else root = root << 1 | 1, lo = mid;

        }

    }



    ll get (int x)

    {

        int root = 1, lo = 0, hi = N; ll ans = INFL;

        while (true) {

        	int mid = (lo + hi) >> 1;

            ans = min(ans, a[root].get(h[x]));

            if (lo + 1 >= hi) return ans;

            if (x < mid) root = root << 1, hi = mid;

            else root = root << 1 | 1, lo = mid;

        }

    }



} tree;



int N;

ll C, h[MAX], f;



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> C;

    for (int i = 0; i < N; ++i) cin >> h[i];

    tree.init(h, N);



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

        f = (i == 0) ? 0ll : (tree.get(i) + h[i] * h[i] + C);

        if (i == N-1) return cout << f << endl, 0;

//        cout << f << ' ';

        tree.upd({-2 * h[i], f + h[i] * h[i]});

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.290080911996436x):
#include <utility>

#include <algorithm>

#include <cstdio>



using namespace std;

using ll = long long;

using pll = pair<ll, ll>;

#define a first

#define b second



static const int MAXN = 200100;



static pll pnts[MAXN];

struct CHT

{

	int ptr = 0, sz = 0;



	bool bad(pll p0, pll p1, pll p2) { return (p1.a - p0.a) * (p2.b - p0.b) - (p2.a - p0.a) * (p1.b - p0.b) > 0; }

	void add(pll p)

	{

		while (sz > 1 && bad(pnts[sz - 2], pnts[sz - 1], p)) --sz;

		pnts[sz++] = p;

	}

	ll val(int i, ll x) { return pnts[i].a * x + pnts[i].b; }

	ll get(ll x)

	{

		ptr = min(ptr, sz - 1);

		while (ptr < sz - 1 && val(ptr, x) > val(ptr + 1, x)) ++ptr;

		return val(ptr, x);

	}

} cht;



int N;

ll h, c, f;



int main()

{

	scanf("%d %lld", &N, &c);

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

		scanf("%lld", &h);

		f = (i == 0 ? 0 : cht.get(h) + h * h + c);

		cht.add(pll(-2 * h, h * h + f));

	}

	printf("%lld\n", f);

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdio>



using namespace std;



using ll = long long;

struct Line { ll a, b; ll get(ll x) { return a * x + b; } };



static const int MAX = 2e5 + 9;

const ll INFL = 1e17;



struct LiChaoTree

{

	int N;

    Line a[MAX << 2];

    ll h[MAX];



    void init (ll _h[MAX], int _N)

    {

    	N = _N;

    	copy (_h, _h + N, h);

    	for (int i = 0; i < N << 2; ++i) a[i] = {0, INFL};

    }



    void upd (Line ln)

    {

        int root = 1, lo = 0, hi = N;

        while (true) {

			int mid = lo + hi >> 1;

            if (ln.get(h[mid]) < a[root].get(h[mid])) swap (ln, a[root]);

//            cerr << '[' << h[lo] << ", " << h[hi-1] << "]: " << a[root].a << ' ' << a[root].b << endl;

            if (lo + 1 >= hi) return;

            if (ln.get(h[lo]) < a[root].get(h[lo])) root = root << 1, hi = mid;

            else root = root << 1 | 1, lo = mid;

        }

    }



    ll get (int x)

    {

        int root = 1, lo = 0, hi = N; ll ans = INFL;

        while (true) {

        	int mid = lo + hi >> 1;

            ans = min(ans, a[root].get(h[x]));

            if (lo + 1 >= hi) return ans;

            if (x < mid) root = root << 1, hi = mid;

            else root = root << 1 | 1, lo = mid;

        }

    }



} tree;



int N;

ll C, h[MAX], f;



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> C;

    for (int i = 0; i < N; ++i) cin >> h[i];

    tree.init(h, N);



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

        f = (i == 0) ? 0ll : (tree.get(i) + h[i] * h[i] + C);

        if (i == N-1) return cout << f << endl, 0;

//        cout << f << ' ';

        tree.upd({-2 * h[i], f + h[i] * h[i]});

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.290080911996436x):
#include <utility>

#include <algorithm>

#include <cstdio>



using namespace std;

using ll = long long;

using pll = pair<ll, ll>;

#define a first

#define b second



static const int MAXN = 200100;



static pll pnts[MAXN];

struct CHT

{

	int ptr = 0, sz = 0;



	bool bad(pll p0, pll p1, pll p2) { return (p1.a - p0.a) * (p2.b - p0.b) - (p2.a - p0.a) * (p1.b - p0.b) > 0; }

	void add(pll p)

	{

		while (sz > 1 && bad(pnts[sz - 2], pnts[sz - 1], p)) --sz;

		pnts[sz++] = p;

	}

	ll val(int i, ll x) { return pnts[i].a * x + pnts[i].b; }

	ll get(ll x)

	{

		ptr = min(ptr, sz - 1);

		while (ptr < sz - 1 && val(ptr, x) > val(ptr + 1, x)) ++ptr;

		return val(ptr, x);

	}

} cht;



int N;

ll h, c, f;



int main()

{

	scanf("%d %lld", &N, &c);

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

		scanf("%lld", &h);

		f = (i == 0 ? 0 : cht.get(h) + h * h + c);

		cht.add(pll(-2 * h, h * h + f));

	}

	printf("%lld\n", f);

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

#define ll long long int

using namespace std;



int main()

{

    ll n,a[100000+9],b[100000+9]= {0},i,j,f=0,c=0;

    cin>>n;

    for(i=0; i<n; i++)

    {

        cin>>a[i];

        b[i]=a[i];

    }

    sort(a,a+n);

    for(i=0; i<n; i++)

    {

        if(a[i]!=b[i])

        {

            f=1;

            c++;

        }

    }



    if(f==0)

    {

        cout<<"YES"<<endl;

    }

    else if(f==1)

    {

        if(c==2)

        {

            cout<<"YES"<<endl;

        }

        else

        {

            cout<<"NO"<<endl;

        }

    }

    return 0;

}


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

using namespace std;

#define ll long long

int main()

{

    ll n,i,j,k,l,a,b,c,d;

    cin>>n;

    ll arr[n+10];

    c=0;

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

    {

        cin>>arr[i];

    }

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

    {

        if(arr[i]!=i)

        {

            for(j=i+1;j<=n;j++)

            {

                if(arr[j]==i)

                {

                    arr[j]=arr[i];

                    arr[i]=i;

                    break;

                    break;



                }

            }

            break;

        }

    }

    c=-1;

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

    {

        if(arr[i]==i){c=1;}

        else{c=0;break;}

    }

    if(c==1)

    {

        cout<<"YES"<<endl;

    }

    else if(c==0)

    {

        cout<<"NO"<<endl;

    }

    return 0;

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

#define ll long long int

using namespace std;



int main()

{

    ll n,a[100000+9],b[100000+9]= {0},i,j,f=0,c=0;

    cin>>n;

    for(i=0; i<n; i++)

    {

        cin>>a[i];

        b[i]=a[i];

    }

    sort(a,a+n);

    for(i=0; i<n; i++)

    {

        if(a[i]!=b[i])

        {

            f=1;

            c++;

        }

    }



    if(f==0)

    {

        cout<<"YES"<<endl;

    }

    else if(f==1)

    {

        if(c==2)

        {

            cout<<"YES"<<endl;

        }

        else

        {

            cout<<"NO"<<endl;

        }

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8053023981873737x):


///HELLO THERE~!

///CREATED BY MD SADMAN MEHEDI SIVAN(IUT CSE[SWE'19])



#include<bits/stdc++.h>

using namespace std;



#define FASTIO          ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

#define READ            freopen("input.txt","r",stdin);

#define WRITE           freopen("red.txt","w",stdout);



using ll=long long;

using ull=unsigned long long;

const double pi = 2*acos(0.0);

const long long MX = 2e5+7;



int main()

{

    FASTIO;

    long long n;

    cin>>n;

    long long a[n+1];

    ll f=0;

    for(ll i=0;i<n;i++)

    {

        cin>>a[i];

        if(a[i]!=i+1)

            f++;

    }

    if(f==0 || f==2)

    {

        cout<<"YES";

    }

    else

        cout<<"NO";







    return 0;







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

#define ll long long int

using namespace std;



int main()

{

    ll n,a[100000+9],b[100000+9]= {0},i,j,f=0,c=0;

    cin>>n;

    for(i=0; i<n; i++)

    {

        cin>>a[i];

        b[i]=a[i];

    }

    sort(a,a+n);

    for(i=0; i<n; i++)

    {

        if(a[i]!=b[i])

        {

            f=1;

            c++;

        }

    }



    if(f==0)

    {

        cout<<"YES"<<endl;

    }

    else if(f==1)

    {

        if(c==2)

        {

            cout<<"YES"<<endl;

        }

        else

        {

            cout<<"NO"<<endl;

        }

    }

    return 0;

}


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

using namespace std;



int main()



{

   long long a=0,b,c,d,e,f,g,h,i,j,k,l,m,n,t;



   cin>>n;



   long long ar[n];



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

   {

       cin>>ar[i];



       if(ar[i]!=i) a++;

   }



   if(a<=2) cout<<"YES"<<endl;



   else if(a>2) cout<<"NO"<<endl;

}