stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



const int N = 3e5 + 10;

string s;

int n, m, v, u, degA[N], degB[N], mark[N];

vector<int> adj_matrix[N], que;



int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);cout.tie(0);

	

	cin >> n >> m;

	cin >> s;

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

		cin >> v >> u;

		v--;u--;

		

		if(v == u){

			adj_matrix[v].push_back(v);

			degA[v] += (s[v] == 'A');

			degB[v] += (s[v] == 'B');

		}

		else{

			adj_matrix[v].push_back(u);

			adj_matrix[u].push_back(v);

			degA[v] += (s[u] == 'A');

			degB[v] += (s[u] == 'B');

			degA[u] += (s[v] == 'A');

			degB[u] += (s[v] == 'B');

		}

		

	}

	

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

		if(degA[i] == 0 || degB[i] == 0)

			que.push_back(i), mark[i] = true;

	

	int i = 0;

	while(que.size() < n && i < que.size()){

		int v = que[i];

		for (int j : adj_matrix[v]){

			if(mark[j])

				continue;

			degA[j] -= (s[v] == 'A');

			degB[j] -= (s[v] == 'B');

			

			if(degA[j] == 0 || degB[j] == 0)

				que.push_back(j), mark[j] = true;

		}

		i++;

	}

	

	if(que.size() < n)

		cout << "Yes";

	else

		cout << "No";

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define reg register

typedef long long ll;

using namespace std;

const int MN=2e5+5;

int deg[MN][2];

int n,m;

char ch[MN];

int to[MN<<1],nxt[MN<<1],h[MN],cnt;

inline void ins(int s,int t){

	to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;

	to[++cnt]=s;nxt[cnt]=h[t];h[t]=cnt;

}

int que[MN],ta;

int main(){

	scanf("%d%d",&n,&m);scanf("%s",ch+1);

	for(reg int i=1,s,t;i<=m;i++){

		scanf("%d%d",&s,&t);ins(s,t);

		deg[s][ch[t]-'A']++;deg[t][ch[s]-'A']++;

	}

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

		if(!deg[i][0]||!deg[i][1])que[++ta]=i;

	for(reg int i=1;i<=ta;i++)

		for(reg int j=h[que[i]];j;j=nxt[j])

			if(deg[to[j]][0]&&deg[to[j]][1]&&!(--deg[to[j]][ch[que[i]]-'A']))

				que[++ta]=to[j];

	puts(ta<n?"Yes":"No");

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

using ll = long long;



vector<int> g[212345];



int main() {

  std::ios::sync_with_stdio(false), std::cin.tie(0);

  int n, m; cin>>n>>m;

  string s;

  cin >> s;

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

    int a, b;

    cin >> a >> b; a--; b--;

    g[a].push_back(b);

    g[b].push_back(a);

  }

  vector<int> ok(n, 1);

  // vector<int> used(n);

  // int col = 1;

  function<void(int)> check = [&](int i) {

    if(!ok[i]) return;

    int f[2] = {};

    for(int j : g[i]) {

      if(ok[j]) f[s[j] == 'A']++;

    }

    if(!(f[0] && f[1])) ok[i] = 0;

    if(!ok[i]) {

      auto newg = g[i];

      for(int j : g[i]) {

        if(!ok[j]) continue;

        check(j);

        if(ok[j]) newg.push_back(j);

      }

      g[i] = newg;

    }

  };

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

  cout << (find((ok).begin(), (ok).end(), 1) != ok.end() ? "Yes" : "No") << endl;

  return 0;

}


// Optimized solution to the same problem (faster):
// includes {{{

#include<iostream>

#include<iomanip>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<tuple>

#include<cmath>

#include<random>

#include<cassert>

// #include<deque>

// #include<multiset>

// #include<bitset>

// #include<cstring>

// #include<bits/stdc++.h>

// }}}

using namespace std;

using ll = long long;



const int N = 2e5;

std::vector<std::vector<int>> g;

int n, m;

string s;



bool ok[N];



void check(int i) {

  if(!ok[i]) return;

  auto ng = g[i];

  ng.clear();

  int cntA = 0, cntB = 0;

  for(int j : g[i]) {

    if(ok[j]) {

      ng.push_back(j);

      if(s[j] == 'A') cntA++;

      else cntB++;

    }

  }

  g[i] = ng;

  if(!cntA || !cntB) {

    ok[i] = 0;

    for(int j : g[i]) {

      check(j);

    }

  }

}



int main() {

  std::ios::sync_with_stdio(false), std::cin.tie(0);

  cin >> n >> m;

  cin >> s;

  g.resize(n);

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

    int a, b; std::cin >> a >> b;

    a--; b--;

    g[a].emplace_back(b);

    g[b].emplace_back(a);

  }



  for(int i = 0; i < n; i++) ok[i] = 1;



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

    check(i);

  }



  bool ans = 0;

  for(int i = 0; i < n; i++) ans |= ok[i];



  cout << (ans ? "Yes" : "No") << endl;



  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define gc() getchar()

using namespace std;

const int maxn=200010,maxm=400010;

int n,m,cnt,head[maxn];

struct edge{

    int from,to,next;

}edges[maxm];

char c[maxn];

bool sz[maxn];

inline bool check(int p){

    char hd;

    if(head[p]<0) return false;

    register int j;

    for(j=head[p];sz[edges[j].to];j=edges[j].next);

    if(j>=0) hd=c[edges[j].to];

    for(;j>=0;j=edges[j].next) if(!sz[edges[j].to]){

        if(c[edges[j].to]!=hd) return true;

    }

    return false;

}

inline void dfs(int p){

    sz[p]=true;

    for(register int j=head[p];j>=0;j=edges[j].next) if((!sz[edges[j].to])&&(!check(edges[j].to))) dfs(edges[j].to);

}

inline void gi (int &x){

    char c;

    for(c=gc();c<'0'||c>'9';c=gc());

    for(x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15);

}

int main(){

    scanf("%d%d",&n,&m);getchar();

    scanf("%s",c+1);int xx,yy;memset(head,-1,sizeof(head));

    for(register int i=1;i<=m;i++){

        gi(xx);gi(yy);

        edges[cnt]=(edge){xx,yy,head[xx]};

        head[xx]=cnt++;

        edges[cnt]=(edge){yy,xx,head[yy]};

        head[yy]=cnt++;

    }

    bool flag;//memset(sz,1,sizeof(sz));

    while(true){

        flag=true;

        for(register int i=1;i<=n;i++) if((!sz[i])&&(!check(i))){

            flag=false;dfs(i);

        }

        if(flag) break;

    }

    for(register int i=1;i<=n;i++) if(!sz[i]){

        printf("Yes\n");return 0;

    }

    printf("No\n");

    return 0;

}

// Optimized solution to the same problem (faster):
#pragma GCC optimize(3)

#include<cstdio>

#include<cstring>

#define gc() getchar()

using namespace std;

const int maxn=200010,maxm=400010;

int n,m,cnt,head[maxn];

struct edge{

    int from,to,next;

}edges[maxm];

char c[maxn];

bool sz[maxn];

inline bool check(int p){

    char hd;

    if(head[p]<0) return false;

    register int j;

    for(j=head[p];sz[edges[j].to];j=edges[j].next);

    if(j>=0) hd=c[edges[j].to];

    for(;j>=0;j=edges[j].next) if(!sz[edges[j].to]){

        if(c[edges[j].to]!=hd) return true;

    }

    return false;

}

inline void dfs(int p){

    sz[p]=true;

    for(register int j=head[p];j>=0;j=edges[j].next) if((!sz[edges[j].to])&&(!check(edges[j].to))) dfs(edges[j].to);

}

inline void gi (int &x){

    char c;

    for(c=gc();c<'0'||c>'9';c=gc());

    for(x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15);

}

int main(){

    scanf("%d%d",&n,&m);getchar();

    scanf("%s",c+1);int xx,yy;memset(head,-1,sizeof(head));

    for(register int i=1;i<=m;i++){

        gi(xx);gi(yy);

        edges[cnt]=(edge){xx,yy,head[xx]};

        head[xx]=cnt++;

        edges[cnt]=(edge){yy,xx,head[yy]};

        head[yy]=cnt++;

    }

    bool flag;//memset(sz,1,sizeof(sz));

    while(true){

        flag=true;

        for(register int i=1;i<=n;i++) if((!sz[i])&&(!check(i))){

            flag=false;dfs(i);

        }

        if(flag) break;

    }

    for(register int i=1;i<=n;i++) if(!sz[i]){

        printf("Yes\n");return 0;

    }

    printf("No\n");

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



string kata;

int len;

int prefixsum[100005];

int tmp;



int main(){

	cin>>kata;

	int r = kata.length();

	len = r;

	int l = 1;

	while(l<r){

		int mid = (l+r+1)>>1;

		

		memset(prefixsum, 0, sizeof(prefixsum));

		tmp =0;

		for(int i=0; i+mid <= len; i++){

			tmp += prefixsum[i];

			int nilpos = (kata[i] - '0') ^ (tmp & 1);

			if(nilpos){

				prefixsum[i+1] ++;

				prefixsum[i+mid] --;

			}

		}

		int sisa  = len - mid;

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

			tmp += prefixsum[i];

			int nilpos = (kata[i] - '0') ^ (tmp & 1);

			if(nilpos == 0) sisa = i;else break;

		}

		if(sisa+1 >= mid){

			l = mid;

		}else{

			r = mid -1;

		}

	}	

	cout<<l<<"\n";

}

// Optimized solution to the same problem (faster):
//C

#include<cstdio> 

#include<iostream>

#include<cstring>

using namespace std;

char s[100010];

int main()

{

	int k=100010,len;

	scanf("%s",s);

	len=strlen(s);

	for(int i=0;i<len;i++)

	{

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

		{

			k=min(k,max(i+1,len-1-i));

		}

	}

	printf("%d",k);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

string s;

int ans=1<<30;

int main()

{

	cin>>s;

	for(int i=1;i<s.length();i++)

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

			ans=min(ans,max(i,int(s.length())-i));

	cout<<min(ans,int(s.length()))<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
/*

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize("Ofast")

#pragma GCC optimize("inline")

#pragma GCC optimize("-fgcse")

#pragma GCC optimize("-fgcse-lm")

#pragma GCC optimize("-fipa-sra")

#pragma GCC optimize("-ftree-pre")

#pragma GCC optimize("-ftree-vrp")

#pragma GCC optimize("-fpeephole2")

#pragma GCC optimize("-ffast-math")

#pragma GCC optimize("-fsched-spec")

#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("-falign-jumps")

#pragma GCC optimize("-falign-loops")

#pragma GCC optimize("-falign-labels")

#pragma GCC optimize("-fdevirtualize")

#pragma GCC optimize("-fcaller-saves")

#pragma GCC optimize("-fcrossjumping")

#pragma GCC optimize("-fthread-jumps")

#pragma GCC optimize("-funroll-loops")

#pragma GCC optimize("-fwhole-program")

#pragma GCC optimize("-freorder-blocks")

#pragma GCC optimize("-fschedule-insns")

#pragma GCC optimize("inline-functions")

#pragma GCC optimize("-ftree-tail-merge")

#pragma GCC optimize("-fschedule-insns2")

#pragma GCC optimize("-fstrict-aliasing")

#pragma GCC optimize("-fstrict-overflow")

#pragma GCC optimize("-falign-functions")

#pragma GCC optimize("-fcse-skip-blocks")

#pragma GCC optimize("-fcse-follow-jumps")

#pragma GCC optimize("-fsched-interblock")

#pragma GCC optimize("-fpartial-inlining")

#pragma GCC optimize("no-stack-protector")

#pragma GCC optimize("-freorder-functions")

#pragma GCC optimize("-findirect-inlining")

#pragma GCC optimize("-frerun-cse-after-loop")

#pragma GCC optimize("inline-small-functions")

#pragma GCC optimize("-finline-small-functions")

#pragma GCC optimize("-ftree-switch-conversion")

#pragma GCC optimize("-foptimize-sibling-calls")

#pragma GCC optimize("-fexpensive-optimizations")

#pragma GCC optimize("-funsafe-loop-optimizations")

#pragma GCC optimize("inline-functions-called-once")

#pragma GCC optimize("-fdelete-null-pointer-checks")

*/

#include <stdio.h>

#include <string.h> 

int ans = 1 << 25;

char str[100010];

int main()

{

	scanf("%s", str);

	int len = strlen(str);

	for (int _ = 1; _ < len; ++ _)

	{

		if (str[_] != str[_ - 1])

		{

			ans = ans > (_ > len - _? _: len - _)? (_ > len - _? _: len - _): ans;

		}

	 } 

	 return !printf("%d\n", ans > len? len: ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

using namespace std;

bool a[100005], c[100005];

int n;

int getans(int k){

	int i;

	memset(c, 0, sizeof(c));

	for(i=2; i<=k; i++){

		c[i]=c[i]^c[i-1];

		if((a[i]^c[i])^(a[i-1]^c[i-1])){

			if(i+k-1>n)

				return false;

			c[i]=!c[i];

			c[i+k-1]=!c[i+k-1];

		}

	}

	return true;

}

int main(){

	int i, l, r, mid;

	char ch;

	

	n=0;

	ch=getchar();

	while(~ch and ch>>5){

		a[++n]=ch&1; 

		ch=getchar();

	}

	l=1;

	r=n;

	while(l<r){

		mid=(l+r+1)>>1;

		if(getans(mid))

			l=mid;

		else

			r=mid-1;

	}

	printf("%d", l);

	return 0;

} 

// Optimized solution to the same problem (faster):
#include "cstdio"

#include "cstring"

int max(int x,int y){

	return x>y?x:y;

}

int min(int x,int y){

	return x<y?x:y;

}

char s[100005];int ss=1e9;

int main(){

	scanf("%s",s);int x=strlen(s);

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

		if(s[i]!=s[i-1])ss=min(ss,max(i,x-i));

	}

	printf("%d\n",min(ss,x));

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
    #include<iostream>

    #include<string>

    #include<algorithm>

    using namespace std;

    int main(){

        string S;

        cin>>S;

        int res=S.size();

        int a=S.size();

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

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

                res=min(res,max(i,a-i));

        }

        cout<<res<<endl;

        return 0;

    }




// Optimized solution to the same problem (faster):
#include "cstdio"

#include "cstring"

int max(int x,int y){

	return x>y?x:y;

}

int min(int x,int y){

	return x<y?x:y;

}

char s[100005];int ss=1e9;

int main(){

	scanf("%s",s);int x=strlen(s);

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

		if(s[i]!=s[i-1])ss=min(ss,max(i,x-i));

	}

	printf("%d\n",min(ss,x));

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int main() {

    string a; 

    int minn = 214748364; 

    cin >> a;

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

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

            minn = min(max(int(a.size()) - i, i), minn);

    if (minn < a.size()) printf("%d\n", minn); else printf("%d\n", a.size());

    return 0;

}

// Optimized solution to the same problem (faster):
#include "cstdio"

#include "cstring"

int max(int x,int y){

	return x>y?x:y;

}

int min(int x,int y){

	return x<y?x:y;

}

char s[100005];int ss=1e9;

int main(){

	scanf("%s",s);int x=strlen(s);

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

		if(s[i]!=s[i-1])ss=min(ss,max(i,x-i));

	}

	printf("%d\n",min(ss,x));

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

int main()

{

    string s;

    while(cin>>s)

    {



    int res=s.size();

    int a=s.size();

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

    {

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

            res=min(res,max(i,a-i));

    }

    cout<<res<<endl;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include<algorithm>

using namespace std;

char s[210000];

int n,ans;

int main()

{

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

    n=strlen(s+1);

    ans=n;

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

    {

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

            ans=min(ans,max(i,n-i));

    }

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

    //system("pause");

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

using namespace std;

char t[100001];

int main()

{

    while(scanf("%s",t)!=EOF)

    {

    int y=strlen(t);

    int max1=y;

    int h=0;

    for(int i=0;i<y;i++)

    {

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

        {

            int u;

            if(y-i-1>i+1)

                u=y-i-1;

            else

                u=i+1;

            if(max1>u)

                max1=u;

        }

    }

    cout<<max1<<endl;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include<algorithm>

using namespace std;

char s[210000];

int n,ans;

int main()

{

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

    n=strlen(s+1);

    ans=n;

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

    {

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

            ans=min(ans,max(i,n-i));

    }

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

    //system("pause");

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string.h>

#define MAXN 100005

using namespace std;



int n, ps[MAXN];

string s;

bool valid(int k){

	memset(ps, 0, sizeof ps);

	int tmp = 0;

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

		tmp += ps[i];

		int now = (s[i]	- '0') ^ (tmp % 2);

//		cout << i << " # " << tmp << " \n";

		if(!now) continue;

		ps[i+1]++;

		ps[min(i+k, n)]--;

	}

	int r = n - k;

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

		tmp += ps[i];

		int now = (s[i]	- '0') ^ (tmp % 2);

		if(now) break;

		r = i;

	}

//	cout << k << " -> " << r << "\n";

	return r + 1 >= k;

}

int main(){

	ios_base::sync_with_stdio(0);

	cin.tie();

	

	cin >> s;

	n = s.length();

	int l = 1;

	int r = s.length();

	int k = (l + r + 1) / 2;

	while(l < r){

		if(valid(k)) l = k;

		else r = k - 1;

		k = (l + r + 1) / 2;

	}

	cout << l << "\n";

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



using ll = long long;

using ii = pair<int,int>;



const int N = 1e5+10;



int n;

char s[N];



int main() { 

  scanf("%s", s);

  n = strlen(s);

  int j = (n - 1) / 2;

  while(j + 1 < n && s[j + 1] == s[(n - 1) / 2]) j++;

  int ans = j + 1;

  j = (n - 1) / 2;

  while(j - 1 >= 0 && s[j - 1] == s[(n - 1) / 2]) j--;

  ans = min(ans, n - j);

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

  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;





int a[200010], b[200010];

int n, bs;





int mn[800010], tag[800010];

void build(int p, int l, int r) {

	if(l == r) {

		mn[p] = b[l]; tag[p] = 0;

		return ;

	}

	int mid = (l + r)>>1;

	build(p<<1, l, mid); build(p<<1|1, mid + 1, r);

	mn[p] = min(mn[p<<1], mn[p<<1|1]);

}

inline void pd(int p) {

	tag[p<<1]+= tag[p]; mn[p<<1]+= tag[p];

	tag[p<<1|1]+= tag[p]; mn[p<<1|1]+= tag[p];

	tag[p] = 0;

}

void add(int p, int l, int r, int x, int y) {

	if(x > y) return ;

	if(x <= l && r <= y) {

		++tag[p];

		++mn[p];

		return ;

	}

	int mid = (l + r)>>1;

	pd(p); 

	if(x <= mid) add(p<<1, l, mid, x, y);

	if(mid + 1 <= y) add(p<<1|1, mid + 1, r, x, y);

	mn[p] = min(mn[p<<1], mn[p<<1|1]);

}

int query(int p, int l, int r, int x, int y) {

	if(x <= l && r <= y) return mn[p];

	int mid = (l + r)>>1;

	int s1 = 0x7fffffff, s2 = 0x7fffffff;

	pd(p);

	if(x <= mid) s1 = query(p<<1, l, mid, x, y);

	if(mid + 1 <= y) s2 = query(p<<1|1, mid + 1, r, x, y);

	return min(s1, s2);

}

int main() {

	cin >> n;

	for(int i = 1; i <= n; ++i) cin >> a[i];

	memcpy(b, a, sizeof(b)); sort(b+1, b+n+1); bs = unique(b+1, b+n+1) - b - 1;

	build(1, 1, bs);

	long long ans = 0;

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

		int p = lower_bound(b+1, b+bs+1, a[i]) - b;

		ans+= query(1, 1, bs, p, bs) - a[i];

		add(1, 1, bs, 1, p - 1);

	}

	cout << ans << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int a[200010], b[200010];

int n, bs;

int mn[800010], tag[800010];

void build(int p, int l, int r) {

	if(l == r) {

		mn[p] = b[l]; tag[p] = 0;

		return ;

	}

	int mid = (l + r)>>1;

	build(p<<1, l, mid); build(p<<1|1, mid + 1, r);

	mn[p] = min(mn[p<<1], mn[p<<1|1]);

}

inline void pd(int p) {

	tag[p<<1]+= tag[p]; mn[p<<1]+= tag[p];

	tag[p<<1|1]+= tag[p]; mn[p<<1|1]+= tag[p];

	tag[p] = 0;

}

void add(int p, int l, int r, int x, int y) {

	if(x > y) return ;

	if(x <= l && r <= y) {

		++tag[p];

		++mn[p];

		return ;

	}

	int mid = (l + r)>>1;

	pd(p); 

	if(x <= mid) add(p<<1, l, mid, x, y);

	if(mid + 1 <= y) add(p<<1|1, mid + 1, r, x, y);

	mn[p] = min(mn[p<<1], mn[p<<1|1]);

}

int query(int p, int l, int r, int x, int y) {

	if(x <= l && r <= y) return mn[p];

	int mid = (l + r)>>1;

	int s1 = 0x7fffffff, s2 = 0x7fffffff;

	pd(p);

	if(x <= mid) s1 = query(p<<1, l, mid, x, y);

	if(mid + 1 <= y) s2 = query(p<<1|1, mid + 1, r, x, y);

	return min(s1, s2);

}

int main() {

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);

	memcpy(b, a, sizeof(b)); sort(b+1, b+n+1); bs = unique(b+1, b+n+1) - b - 1;

	build(1, 1, bs);

	long long ans = 0;

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

		int p = lower_bound(b+1, b+bs+1, a[i]) - b;

		ans+= query(1, 1, bs, p, bs) - a[i];

		add(1, 1, bs, 1, p - 1);

	}

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

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <stdlib.h>

#include <algorithm>

#include <math.h>

#include <vector>

#include <list>

#include <map>

#include <queue>

#include <set>

using namespace std;



int p[10][10];

int n,m;



int main(){

	while(cin>>n>>m){

		for(int a=0;a<10;a++){

			for(int b=0;b<10;b++){

				cin>>p[a][b];

			}

		}

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

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

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

					p[i][j]=min(p[i][j],p[i][k]+p[k][j]);

				}

			}

		}

		int sum=0;

		for(int a=0;a<n*m;a++){

			int key;

			cin>>key;

			if(!(key==1||key==-1)) sum+=p[key][1];

		}

		cout<<sum<<endl;

	}

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



using namespace std;



int C[10][10];

int h, w;



int main() {

    scanf("%d%d", &h, &w);

    for (int i = 0; i < 10; i++)

        for (int j = 0; j < 10; j++) scanf("%d", &C[i][j]);

    for (int k = 0; k < 10; k++)

        for (int i = 0; i < 10; i++)

            for (int j = 0; j < 10; j++) C[i][j] = min(C[i][j], C[i][k] + C[k][j]);

    int ans = 0;

    for (int i = 0, x; i < h; i++)

        for (int j = 0; j < w; j++) scanf("%d", &x), ans += (x==-1)?0:C[x][1];

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

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// 



#include <vector>

#include <iostream>

#include <queue>

#include <climits>

using namespace std;



#define INF 2000

#define F first

#define S second

typedef pair< int, int > ii;



const int N = 10;



int n, start, finish;

int cost[N][N]; // adjacency matrix

int freq[10]; // number of each digit on the wall



priority_queue< ii, vector< ii >, greater< ii > > pq;



int dist[N];

bool visit[N];



int row, col;



void input ()

{

	cin >> row >> col;

	

	for (int i = 0; i < 10; ++i) 

	for (int j = 0; j < 10; ++j) cin >> cost[j][i]; // reversed

	

	int digit;

	for (int i = 1; i <= row; ++i)

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

		cin >> digit;

		if (digit != -1) ++freq[digit];

	}

}



void init ()

{

	for (int i = 0; i < 10; ++i) dist[i] = INF;

	dist[1] = 0;

	pq.emplace(0, 1);

}



void dijkstra ()

{

	input();

	init();

	

	int proc;

	while (!pq.empty())

	{

		proc = pq.top().second;

		pq.pop();

		

		if (visit[proc]) continue;

		visit[proc] = true;

		

		int temp;

		int adj;

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

			

			adj = i;

			temp = cost[proc][i] + dist[proc];

			

			if (temp < dist[adj]) {

				dist[adj] = temp;

				pq.emplace(temp, adj);

			}

		}

	}

	

	long long ans = 0;

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

		ans += (long long) dist[i]*freq[i];

	}

	

	cout << ans << "\n";

	

	return;

}



int main ()

{

	dijkstra();

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



using namespace std;



int C[10][10];

int h, w;



int main() {

    scanf("%d%d", &h, &w);

    for (int i = 0; i < 10; i++)

        for (int j = 0; j < 10; j++) scanf("%d", &C[i][j]);

    for (int k = 0; k < 10; k++)

        for (int i = 0; i < 10; i++)

            for (int j = 0; j < 10; j++) C[i][j] = min(C[i][j], C[i][k] + C[k][j]);

    int ans = 0;

    for (int i = 0, x; i < h; i++)

        for (int j = 0; j < w; j++) scanf("%d", &x), ans += (x==-1)?0:C[x][1];

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

    return 0;

}

// Fastest known solution for this problem: