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

#include <cstring>

#include <algorithm>

#define ll long long

#define inf 1<<30

#define il inline 

il void readl(ll &x){

    x=0;ll f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    x*=f;

}

il void read(int &x){

    x=0;int f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    x*=f;

}

using namespace std;



#define N 100010

#define lowbit(x) x&-x

int c[N*10];

int n,a[N],s[N*10];

void add(int x){

    for(int i=x;i<=2*N;i+=lowbit(i))c[i]++;

}

ll query(int x){

    ll sum=0;

    for(int i=x;i>0;i-=lowbit(i))sum+=c[i];

    return sum;

}

bool check(int x){

    for(int i=1;i<=2*N;i++)c[i]=0;

    s[0]=0;

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

        s[i]=s[i-1]+(a[i]>=x?1:-1);

    ll sum=0;

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

        sum+=query(s[i]+N);

        add(s[i]+N);

    }

    return sum>=1ll*n*(n+1)/4;

}

int main(){

    read(n);

    int l=0,r=0;

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

        read(a[i]);

        r=max(r,a[i]);

    }

    int ans=0;

    while(l<=r){

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

        if(check(mid)) l=mid+1;

        else r=mid-1;

    }

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

}


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

// Copyright 2020 TuringEdu. All Rights Reserved.

//

// FileName: C.cc

// Author: Beiyu Li <sysulby@gmail.com>

// Date: 2020-06-16

//

#include <bits/stdc++.h>

#include <bits/extc++.h>



using namespace std;



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

#define For(i, s, t) for (int i = (s); i <= (t); ++i)



using LL = long long;

using Pii = pair<int, int>;

template <typename T>

using Heap = __gnu_pbds::priority_queue<T, greater<T>,

      __gnu_pbds::pairing_heap_tag>;

template <typename T>

using BST = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>,

      __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;



const int inf = 0x3f3f3f3f;

const LL infLL = 0x3f3f3f3f3f3f3f3fLL;



const int maxn = 100000 + 5;



int n;

int a[maxn];

int vec[maxn], sz;

int s[maxn], t[maxn];



LL merge_sort(int l, int r) {

  if (l == r) return 0;

  int mid = (l + r) / 2;

  LL ret = merge_sort(l, mid) + merge_sort(mid + 1, r);

  int i = l, j = mid + 1, p = l;

  while (i <= mid || j <= r) {

    if (j > r || (i <= mid && s[i] <= s[j])) t[p++] = s[i++];

    else t[p++] = s[j++], ret += mid - i + 1;

  }

  For(i,l,r) s[i] = t[i];

  return ret;

}



bool check(int x) {

  s[0] = 0;

  For(i,1,n) s[i] = s[i-1] + (a[i] < x? -1: 1);

  return merge_sort(0, n) * 2 <= (LL)n * (n + 1) / 2;

}



int main() {

  scanf("%d", &n);

  For(i,1,n) {

    scanf("%d", &a[i]);

    vec[sz++] = a[i];

  }

  sort(vec, vec + sz);

  sz = unique(vec, vec + sz) - vec;

  int l = 0, r = sz - 1;

  while (l < r) {

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

    if (check(vec[mid])) l = mid;

    else r = mid - 1;

  }

  printf("%d\n", vec[l]);



  return 0;

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

using namespace std;

int ar[100009][3];

void clr()

{

	int i,j;

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

	{

		ar[i][0]=0;

		ar[i][1]=0;

	}

}

int main()

{

	 string st;

	 clr();

   int ac=0,wa=0,i,j,n,s,id;

   cin>>n>>s;

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

   {

      cin>>id>>st;

      if(ar[id][0]==0 && st=="WA") ar[id][1]++;

      if(ar[id][0]==0 && st=="AC") ar[id][0]=1;

   }



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

   {

   	 if(ar[i][0]==1)

   	 {

   	 	ac++;

   	 	wa+=ar[i][1];

   	 }

   }

   cout<<ac<<" "<<wa<<endl;

   return 0;

   

}

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

#include<iostream>

using namespace std;

int a[100010]={0};

int main()

{

	int n,m,i;

	cin>>n>>m;

	int x=0,y=0;

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

	{

		int s;string ss;

		cin>>s>>ss;

		if(a[s]>=0)

		{

			if(ss=="WA")

			{

				a[s]++;

			}

			else

			{

				x+=a[s];

				a[s]=-1;

				y++;

				

			}

		}

	}

	printf("%d %d\n",y,x);

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



using namespace std;

typedef long long ll;



ll n,arr[100005],mem[100005],k;



ll dp(ll pos){

    if(pos==n-1)return 0;

    if(pos>=n)return 10000000000;

    ll res=10000000000;

    if(mem[pos]!=-1)return mem[pos];

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

        if(i<n)res=min(res,dp(i)+abs(arr[pos]-arr[i]));

    }

    return mem[pos]=res;

}



int main(){

    ios_base::sync_with_stdio(0);

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

    cin>>n>>k;

    memset(mem,-1,sizeof(mem));

    for(int i=0;i<(int)n;i++)cin>>arr[i];

    cout<<dp(0);

}

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



using namespace std;

typedef long long ll;



ll n,arr[100005],dp[100005],k;



int main(){

    ios_base::sync_with_stdio(0);

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

    cin>>n>>k;

    for(int i=0;i<(int)n;i++)cin>>arr[i];

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

        dp[i]=1000000000;

    }

    dp[0]=0;

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

        for(int j=i-1;j>=(max((ll)0,i-k));j--){

            dp[i]=min(dp[i],dp[j]+abs(arr[j]-arr[i]));

        }

    }

    cout<<dp[n-1];

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

using namespace std;

typedef long long int ll;

#define faster ios_base::sync_with_stdio(0);

#define faster_tie cin.tie(0);

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

#define NL cout<<'\n'



ll n,k,x;

vector<ll>height;

vector <ll> sol(110000,-1);



ll solve(ll x)

{

    if(x==1)

    {

        sol[x]=0;

        return 0;

    }

    if(sol[x]!=-1)return sol[x];

    ll a=INT_MAX;



    for(ll i=x-1;i>x-1-k;i--)

    {

        if(i==0)break;

        a=min(a,solve(i)+abs(height[i]-height[x]));

    }

    sol[x]=a;

    return a;



}





int main()

{

    cin>>n>>k;

    height.push_back(-1);

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

    {

        sol[i]=-1;

    }

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

    {

        cin>>x;

        height.push_back(x);

    }



    ll ans=solve(n);

    cout<<ans;







    return 0;

}


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

using namespace std;

typedef long long int ll;

#define pb push_back

#define mp make_pair



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);



    ll n,k;

    cin>>n>>k;



    vector<ll>h(n+1);

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

    {

        cin>>h[i];

    }



    vector<ll>cost(n+5);

    cost[1]=0;



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

    {

        ll c=LONG_MAX;

        for(ll j=i-1;j>i-k-1&&j>0;j--)

        {

            c=min(c,cost[j]+abs(h[i]-h[j]));

        }

        cost[i]=c;

    }



    cout<<cost[n]<<endl;



    return 0;

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

using namespace std;

 

vector<int> vec;

vector<int> dp(100001,-1);

 

int back(int i,int k){

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

        if(i+j==vec.size()-1) return abs(vec[i+j]-vec[i]);

    }

    // if(i+2==vec.size()-1) return abs(vec[i+2]-vec[i]);

    if(dp[i]!=-1) return dp[i];

    

    int ans=INT_MAX;

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

        if(i+j<vec.size()){

            ans= min(ans, abs(vec[i+j]-vec[i]) + back(i+j,k));

        }

    }

 

    dp[i]=ans;

    return dp[i];

}

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n,k;

    cin>>n>>k;

    

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

        int a;

        cin>>a;

        vec.push_back(a);

    }

    cout<<back(0,k);

	return 0;

}

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

using namespace std;

 

int mincost(int n ,int k,vector<int>&height)

{

     vector<int>dp(n,INT_MAX);

     dp[0]=0;

     dp[1] = abs(height[1]-height[0]);

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

     {  for(int j =i-1;j>=0&&j>=i-k;j--)

          if(i>j)

          dp[i] = min(dp[i],dp[j]+abs(height[i]-height[j]));

     }

    return dp[n-1];

}

int main(){

    int n,k ;

  cin>>n>>k;

  vector<int>height(n);

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

  {  cin>>height[i];

  }

  cout<<mincost(n,k,height)<<endl;

  

  return 0;

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

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<iomanip>

#include<vector>

using namespace std;

int main()

{

	int k,i;

	cin>>k;

	string s;

	cin>>s;

	int len=s.size();

	if(len<=k)cout<<s<<endl;

	else 

	{

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

		{

			cout<<s[i];

		}

		cout<<"..."<<endl;

	}

	return 0;

 } 

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

	# include <string.h>

	int main () {

		int a = 0;

		int c =0;

	char name [100];

		scanf ("%d",&a);

		scanf("%s%[^\n]",&name);

		c = strlen (name);

		if (c<=a) {

			printf ("%s",name);

		} else if (c>a) {

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

				printf ("%c",name[i]);

			}

			printf("...");

		}

		return 0;

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

using namespace std;

int main(){

    int k;

    char s[105];

    cin>>k;cin>>s;

    if(strlen(s)<=k) cout<<s;

    else {

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

            cout<<s[i];

        cout<<"...";

    }

    return 0;

}

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

#include<string.h>

int main(){

	int k;

	char s[105];

	scanf("%d",&k);

	getchar();

	scanf("%s",&s);

	if(strlen(s)>k){

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

			printf("%c",s[i]);

		}

		printf("...");

		printf("\n");

	}

	else{

		int l = strlen(s);

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

			printf("%c",s[i]);

		printf("\n");

	}

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

typedef long long ll;

using namespace std;

const int N = 1e5 + 10;

ll dp[1 << 18];

int a[1 << 18];

int main() {

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

    int n, c = 0;

    ll mx;

    cin >> n;

    mx = (1 << n);

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

        cin >> a[i];

    }

    for(int i = 0; i < mx; i++) dp[i] = mx*i;

    ll ans = 0;

    for(int s = 1; s < mx; s++) {

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

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

                int s0 = s ^ (1 << i);

                ll tmp[4] = {dp[s0]%mx, dp[s0]/mx, dp[s]/mx, dp[s]%mx};

                sort(tmp, tmp + 4, [&](ll x, ll y){return a[x]>a[y];});

                unique(tmp, tmp + 4);

                dp[s] = tmp[0]+tmp[1]*mx;

            }

        }

        ll res = a[dp[s]/mx] + a[dp[s]%mx];

        ans = max(ans, res);

        cout << ans << endl;

    }

    return 0;

}

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

#include <cstdio>

#include <cstring>



#define int long long



const int Maxv = 300010; 



int ans[Maxv], max[Maxv], num, n; 



signed main() {

    scanf("%lld", &n); 

    

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

        scanf("%lld", &num); 

    

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

            ans[j] = std::max(ans[j], max[j] + num); 

            max[j] = std::max(max[j], num); 

        }

    }

       

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

        printf("%lld\n", ans[i]); 

        ans[i + 1] = std::max(ans[i + 1], ans[i]); 

    }

    

    return 0; 

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

#include<cstring>

#include<cstdio>

#define ll long long

using namespace std;

const int N=100000+7;

int n,a[N],l,r,mid,c[3*N],t[N];

ll s[N];

int lowbit(int x){

	return x&-x;

}

void add(int x){

	for(int i=x;i<=2*N;i+=lowbit(i))

		c[i]++;

}

int query(int x){

	ll sum=0;

	for(int i=x;i>=1;i-=lowbit(i))

		sum+=c[i];

	return sum;

}

bool check(int now){

    for(int i=1;i<=2*N;i++)c[i]=0;		//用memset会出错 

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

		s[i]=s[i-1]+(a[i]>=now ?1 :-1);

		//if(now==9)printf("%d ",s[i]);

	}

	//printf("\n");

	ll sum=0;

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

		sum+=query(s[i]+N);

		add(s[i]+N);

	}

	//printf("%d %d\n",now,sum);

	return sum>=1ll*n*(n+1)/4;

}

int main(){

	//freopen("1.txt","r",stdin);

	cin>>n;

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

		scanf("%d",&a[i]);

		r=max(r,a[i]);

	}

	while(l<=r){			//一定要用 <=，不然会漏情况 

		mid=(l+r)>>1;

		if(check(mid))l=mid+1;

		else r=mid-1;

	}

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

	return 0;

}

/*

3

10 30 20



*/

/*

10

5 9 5 9 8 9 3 5 4 3



*/

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

using namespace std;



const int N = 110000;



int a[N], sum[N];

int BIT[3 * N];



int main() {

	

	ios::sync_with_stdio(0);

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

	

	int n; cin >> n;

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

	

	int st = 0, en = 1e9, mid, ans = en;

	

	auto add = [&](int u, int v) {

		for (int i = u; i <= 3 * (n + 1); i += i & -i) BIT[i] += v;

	};

	

	auto get = [&](int u) {

		int ret = 0;

		for (int i = u; i > 0; i -= i & -i) ret += BIT[i];

		return ret;

	};

	

	auto can = [&](int mid) {

		sum[0] = 0;

		for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + 2 * (a[i] <= mid);

		for (int i = 0; i <= 3 * (n + 1); i++) BIT[i] = 0;

		long long cnt = 0;

		add(0 + n + 1, 1);

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

			cnt += get(sum[i] - i + n);

			add(sum[i] - i + n + 1, 1);

		}

		return cnt * 2 > (long long)n * (n + 1) / 2;

	};

	

	while (st <= en) {

		mid = st + en >> 1;

		if (can(mid)) ans = mid, en = mid - 1;

		else st = mid + 1;

	}

	cout << ans << "\n";

	

	return 0;

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

using namespace std;

#define N (int)2e5

int n,k,memo[N],c[N];



int dp(int curr) {

    if (curr == n) return 0;

    if (curr > n) return 1e9;

    int &sol = memo[curr];

    if (sol != -1) return sol;

    int keep = INT_MAX;

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

        keep = min(

            dp(curr + i) + abs(c[curr] - c[curr + i]) ,

            keep

        );

    }

    return sol = keep;

}



int main() {

    scanf("%d%d" , &n , &k);

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

        scanf("%d" , &c[i]);

    memset (memo , -1 , sizeof memo);

    printf("%d\n" , dp(1));

}


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

using namespace std;

typedef long long LL;



int arr[100007];

int dp[100007];



int Solve(int idx, int n, int k){

//	cout<<cost<<" "<<idx<<endl;

	if(idx >= n)return 1e9;

	if(idx == n - 1){

		return 0;	

	}

	

	if(dp[idx] != -1)return dp[idx];

	

	int ans = 1e9;

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

		ans = min(ans, abs(arr[idx] - arr[idx+i]) + Solve(idx+i, n, k));

	}

	

	return dp[idx] = ans;

}



int main(){

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

	memset(dp,-1,sizeof(dp));

	for(int i = 0; i < n; i++)cin>>arr[i];

		

	cout<<Solve(0,n,k)<<endl;

	return 0;

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

using namespace std;

const int N=1e5+1;

vector<int> h(N);

const int INF=1e9+5;

vector<int> dp(N,-1);

int n,k;

int f(int i){

    if(dp[i]!=-1) return dp[i];

    if(i==n) return 0;

    if(i>n) return INF;

    int p = INF;    

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

        p=min(p,f(i+j)+abs(h[i]-h[i+j]));

    }

    return dp[i]=p;

}

int main(){

    scanf("%d%d",&n,&k);

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

        scanf("%d",&h[i]);

    }

    cout<<f(1)<<'\n';

    // while(1);

    return 0;

}

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

#include "stdafx.h"

#include<iostream>

#include<vector>

#include<algorithm>

#include<queue>

#include<stack>

#include<cmath>

#include<complex>

*/



#include<bits/stdc++.h>



#define X real()

#define Y imag()

#define pb push_back

#define ppb pop_back

#define mp make_pair

#define ff first

#define ss second

#define FastF freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)

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

using ll = long long;

using namespace std;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

typedef vector<int> vi;

typedef vi::iterator vii;

typedef vector<ll> vl;

typedef vl::iterator vli;

typedef long double C;

typedef complex<C> P;

const int INF = 1e9 + 5;

const ll INFF = 1e18 + 5;

const int M = 1e9 + 7;

const double pi = acos(-1);



int main()

{

	//FastF;

	Fast;

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

	vi h(n + 1);

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

		cin >> h[i];

	}

	vi dp(n + 1,INF);

	dp[1] = 0;

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

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

			if (j > n) continue;

			dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));

		}

	}

	cout << dp[n] << '\n';

	return 0;

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

using namespace std;

int main()

{

	int n;

	string inp;

	cin>>n;

	getchar();

	cin>>inp;

	long long size=inp.size(),j,i,red=0,green=0,blue=0;

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

		if(inp[i]=='R') red++;

		else if(inp[i]=='G') green++;

		else blue++;

	}

	long long ans=red*green*blue;

	for(i=0 ; i<size-2 ; i++){

		for(j=i+1 ; j<size-1; j++){

			long long k=2*j - i;

		//	cout<<i<<" "<<j<<" "<<k<<endl;

			if(k<size){

				if(inp[i]+inp[j]+inp[k]=='R'+'G'+'B') ans--;}

		}

	}

	cout<<ans<<endl;

	return 0;

}

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

#include<algorithm>



using namespace std;



typedef long long LL;



const int N = 4010;



int r[N], g[N], b[N];

char s[N];



int main()

{

    int n;

    scanf("%d", &n);

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

    

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

    {

        r[i] = r[i - 1], g[i] = g[i - 1], b[i] = b[i - 1];

        if(s[i] == 'R')  r[i] ++;

        else if(s[i] == 'G')  g[i] ++;

        else  b[i] ++;

    }

    

    LL res = 0;

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

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

            if(s[i] != s[j])

            {

                char c = (int)'R' + 'G' + 'B' - s[i] - s[j];

                if(c == 'R')  res += r[i - 1];

                else if(c == 'G')  res += g[i - 1];

                else  res += b[i - 1];

                if(i - (j - i) >= 1 and s[i - (j - i)] == c)  res --;

            }

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

    return 0;

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

#include <string>



using namespace std;



int main()

{

    int n;

    string s;

    cin >> n >> s;

    if (s.size()<=n)cout << s;

    else 

    {

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

        {

            cout << s[i];

        }

        cout << "...";

    }

    

    return 0;

}


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



int main(){

	int k;

	char word[100];

	scanf("%d", &k);

	scanf("%s", &word);

	

	int len = 0;

	

	for(int i = 0; word[i] != '\0'; i++){

		len++;

	}

	

	if(len <= k){

		printf("%s\n", word);

	}

	else{

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

			printf("%c", word[i]);

		}

		printf("...\n");

	}

	return 0;

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

#include <cstring>

#include <map>

#include <algorithm>

using namespace std;

const int SIZEN = 500010;

int N;

map<long long ,int> mp;

int main(){

	scanf("%d",&N);

	long long ans = 0;

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

		long long x;

		scanf("%lld",&x);

		mp[x]++;

		ans += x;

	}

	int M;

	scanf("%d",&M);

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

		long long x,y;

		scanf("%lld%lld",&x,&y);

		ans -= x * mp[x];

		ans += y * mp[x];

		mp[y] += mp[x];

		mp[x] = 0;printf("%lld\n",ans);

	}

	

	return 0;

}

/*

4

1 1 1 1

3

1 2

2 1

3 5

*/

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

using namespace std;



int num[100050];



int main()

{

	long long sum=0;

	int N,Q,B,C,a;

	scanf("%d",&N);

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

		num[i]=0;

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

	{

		scanf("%d",&a);

		sum+=(long long)a;

		++num[a];

	}

	scanf("%d",&Q);

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

	{

		scanf("%d%d",&B,&C);

		sum+=(long long)(C-B)*num[B];

		num[C]+=num[B];

		num[B]=0;

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

	}

return 0;

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

using namespace std;

int dp[200005];

int a[200005];

int main()

{

    int n,k;

    cin>>n>>k;



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

    dp[2]=abs(a[2]-a[1]);

    for(int i=3; i<=n; i++) dp[i]=INT_MAX;

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

    {

        for(int j=max(1,i-k); j<i; j++)

        {

            dp[i]=min(dp[i],(dp[j]+abs(a[i]-a[j])));

        }



    }

    cout<<dp[n]<<endl;

}


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

#include<algorithm>



int main(){

  int s,k;

  long long st[100001],p[100001];

  scanf("%d%d",&s,&k);

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

    scanf("%lld",&st[i]);

  }

  p[0]=0;

  p[1]=0;

  p[2]=(st[2]-st[1] < 0) ? st[1]-st[2] : st[2]-st[1];

  for(int i=3;i<=s;i++){

    p[i] = 1000000001;

  }

  for(int i=3;i<=s;i++){

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

      if(i-j>=1){

	long long tmp;

	tmp = (st[i]-st[i-j] < 0) ? st[i-j]-st[i] : st[i]-st[i-j];

	if(p[i] > p[i-j]+tmp){

	  p[i] = p[i-j]+tmp;

	}

	if(tmp == 0) break;

      }else{

	break;

      }

    }

  }

  printf("%lld\n",p[s]);

  return 0;

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

#include<cstring>

using namespace std;

char a[100001];int b[100001];

int main(){

	cin>>a;

	int n=0;

	for(int i=0;i<strlen(a);i++){

		if(a[i]=='0'){

			b[n]=0;

			n++;

		}

		else if(a[i]=='1'){

			b[n]=1;

			n++;

		}

		else{

			if(n==0)continue;

			else{

				n--;

			}

		}

	}

	for(int i=0;i<=n-1;i++)cout<<b[i];

	return 0;

}

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

#include<cstring>

using namespace std;

char s[20], S[20];

int main()

{

	scanf("%s", s);

	int len = strlen(s);

	int cnt = 0;

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

	{

		if(s[i] == '1')

		{

			S[cnt] = '1';

			cnt++;

		}

		if(s[i] == '0')

		{

			S[cnt] = '0';

			cnt++;

		}

		if(s[i] == 'B')

		{

			if(cnt)cnt--;

			S[cnt] = '\0';

		}

	}

	printf("%s\n", S);

	return 0;

}