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

using namespace std;

const int maxn = 1e5+5;

int pa[maxn];

int f(int x) {

    return x == pa[x] ? x : (pa[x] = f(pa[x]));

}

void un(int x, int y) {

    int px = f(x);

    int py = f(y);

    if (px != py) {

        pa[px] = py;

    }

}

int main() {

    int n, m;

    cin >> n >> m;

    vector<int> nums(n+1);

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

        cin >> nums[i];

    }

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

        pa[i] = i;

    }

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

        int x, y;

        cin >> x >> y;

        un(x, y);

    }

    int ans = 0;

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

        if (f(nums[i]) == f(i)) {

            ans++;

        }

    }

    cout << ans << "\n";

    return 0;

}

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



void optimize_cpp_stdio() {

    std::ios::sync_with_stdio(false);

    std::cout.tie(nullptr);

    std::cin.tie(nullptr);

}



int main() {

    optimize_cpp_stdio();

    int n, m;

    std::cin >> n >> m;

    std::vector<int> a(n);

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

        std::cin >> a[i];

        --a[i];

    }

    std::vector<std::vector<int>> G(n);

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

        std::cin >> u >> v;

        G[--u].push_back(--v);

        G[v].push_back(u);

    }

    int ans = 0;

    std::vector<bool> vis(n);

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

        if (vis[i]) continue;

        std::vector<int> index, value;

        std::queue<int> q({i});

        vis[i] = true;

        for (; !q.empty(); q.pop()) {

            int u = q.front();

            index.push_back(u);

            value.push_back(a[u]);

            for (int v : G[u]) {

                if (vis[v]) continue;

                vis[v] = true;

                q.push(v);

            }

        }

        std::sort(index.begin(), index.end());

        for (int it : value)

            ans += std::binary_search(index.begin(), index.end(), it);

    }

    std::cout << ans << "\n";

    return 0;

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

using namespace std;



const int N = 1e5 + 10;



vector <int> G[N];

vector <int> sav;

int a[N], rec[N];



void dfs(int x, int id){

	rec[x] = id;

	sav.push_back(a[x]);

	for (int i = 0; i < (int)G[x].size(); i++){

		if (!rec[G[x][i]]) dfs(G[x][i], id);

	}

}



int main(){

	int n, m, u, v, ans;

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

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

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

		scanf("%d %d",&u,&v);

		G[u].push_back(v);

		G[v].push_back(u);

	}

	memset(rec, 0, sizeof(rec));

	ans = 0;

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

		if (!rec[i]){

			sav.clear();

			dfs(i, i);

			for (int j = 0; j < (int)sav.size(); j++){

				if (rec[sav[j]] == i) ans++;

			}

		}

	}

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

	return 0;

}

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



void optimize_cpp_stdio() {

    std::ios::sync_with_stdio(false);

    std::cout.tie(nullptr);

    std::cin.tie(nullptr);

}



int main() {

    optimize_cpp_stdio();

    int n, m;

    std::cin >> n >> m;

    std::vector<int> a(n);

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

        std::cin >> a[i];

        --a[i];

    }

    std::vector<std::vector<int>> G(n);

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

        std::cin >> u >> v;

        G[--u].push_back(--v);

        G[v].push_back(u);

    }

    int ans = 0;

    std::vector<bool> vis(n);

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

        if (vis[i]) continue;

        std::vector<int> index, value;

        std::queue<int> q({i});

        vis[i] = true;

        for (; !q.empty(); q.pop()) {

            int u = q.front();

            index.push_back(u);

            value.push_back(a[u]);

            for (int v : G[u]) {

                if (vis[v]) continue;

                vis[v] = true;

                q.push(v);

            }

        }

        std::sort(index.begin(), index.end());

        for (int it : value)

            ans += std::binary_search(index.begin(), index.end(), it);

    }

    std::cout << ans << "\n";

    return 0;

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

#define ll long long



using namespace std;



int n,m;

int p[100010];

vector<int> graf[100010];

int mark[100010];

int flag=1;



void bfs(int c)

{

    if(mark[c]==0)

        mark[c]=flag;

    else

        return;

    for(int i=0;i<graf[c].size();i++)

        if(mark[graf[c][i]]==0)

            bfs(graf[c][i]);

}



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



    cin>>n>>m;

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

        cin>>p[i];

    int x,y;

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

    {

        cin>>x>>y;

        graf[x].push_back(y);

        graf[y].push_back(x);

    }



    int sol=0;

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

    {

        if(mark[i]==0)

            bfs(i), flag++;

    }

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

        if(mark[p[i]]==mark[i])

            sol++;

    cout<<sol;

	return 0;

}


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



void optimize_cpp_stdio() {

    std::ios::sync_with_stdio(false);

    std::cout.tie(nullptr);

    std::cin.tie(nullptr);

}



int main() {

    optimize_cpp_stdio();

    int n, m;

    std::cin >> n >> m;

    std::vector<int> a(n);

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

        std::cin >> a[i];

        --a[i];

    }

    std::vector<std::vector<int>> G(n);

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

        std::cin >> u >> v;

        G[--u].push_back(--v);

        G[v].push_back(u);

    }

    int ans = 0;

    std::vector<bool> vis(n);

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

        if (vis[i]) continue;

        std::vector<int> index, value;

        std::queue<int> q({i});

        vis[i] = true;

        for (; !q.empty(); q.pop()) {

            int u = q.front();

            index.push_back(u);

            value.push_back(a[u]);

            for (int v : G[u]) {

                if (vis[v]) continue;

                vis[v] = true;

                q.push(v);

            }

        }

        std::sort(index.begin(), index.end());

        for (int it : value)

            ans += std::binary_search(index.begin(), index.end(), it);

    }

    std::cout << ans << "\n";

    return 0;

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

#include <cstring>

#include <iostream>

#include <string>

#include <cmath>

#include <bitset>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <algorithm>

#include <complex>

#include <unordered_map>

#include <random>

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;

vector<int> g[100000];

int  used[100000];

int used2[100000];

int p[100000];

int c;

void dfs(int x){

    used[x]=c;

    used2[p[x]]=c;

    for(auto y:g[x]){

        if(!used[y]) dfs(y);

    }

}

int main()

{

	int n, m;

	cin>>n>>m;

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

        cin>>p[i]; p[i]--;

    }

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

        int x, y;

        cin>>x>>y;

        x--; y--;

        g[x].push_back(y);

        g[y].push_back(x);

    }

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

        if(used[i]) continue;

        c++;

        dfs(i);

    }

    int ans=0;

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

        if(used[i]==used2[i]) ans++;

    }

    cout<<ans<<endl;

	return 0;

}

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

#include <cstring>

#include <iostream>

#include <string>

#include <cmath>

#include <bitset>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <algorithm>

#include <complex>

#include <unordered_map>

#include <random>

using namespace std;

typedef long long int ll;

typedef pair<int, int> P;

int par[100002];

int rk[100002];

int p[100000];

void init(int n){

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

		par[i]=i;

	}

}



int find(int x){

	if(par[x]==x){

		return x;

	}else{

		return par[x]=find(par[x]);

	}

}

 

void unite(int x, int y){

	x=find(x);

	y=find(y);

	if(x==y) return;

	if(rk[x]<rk[y]){

		par[x]=y;

	}else{

		par[y]=x;

		if(rk[x]==rk[y]) rk[x]++;

	}

}

 

bool same(int x, int y){

	return find(x)==find(y);

}

int main()

{

	int n, m;

	cin>>n>>m;

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

        cin>>p[i]; p[i]--;

    }

    init(n);

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

        int x, y;

        cin>>x>>y;

        x--; y--;

        unite(x, y);

    }

    int p2[100000];

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

        p2[p[i]]=find(i);

    }

    int ans=0;

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

        if(p2[i]==find(i)) ans++;

    }

    cout<<ans<<endl;

	return 0;

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

#include <array>



std::array<int, 100005> p;

std::array<int, 100005> fa;



int find(int x){return fa[x]^x?fa[x]=find(fa[x]):x;}



int main()

{

    int n, m;

    std::cin >> n >> m;

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

    {

        int temp;

        std::cin >> temp;

        p[i] = temp;

        fa[i] = i;

    }



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

    {

        int u, v;

        std::cin >> u >> v;



        fa[find(u)] = find(v);

    }



    int count = 0;

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

    {

        if (find(p[i - 1]) == find(i))

        {

            count++;

        }

    }

    std::cout << count << std::endl;

}


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

#include <array>



std::array<int, 100005> p;

std::array<int, 100005> fa;



int find(int x)

{

    if (fa[x] != x)

    {

        fa[x] = find(fa[x]);

        return fa[x];

    }

    else

    {

        return x;

    }

}



int main()

{

    int n, m;

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

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

    {

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

        fa[i] = i;

    }

    int u, v;

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

    {

        scanf("%d %d", &u, &v);

        fa[find(u)] = find(v);

    }



    int count = 0;

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

    {

        if (find(p[i - 1]) == find(i))

        {

            count++;

        }

    }

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

}
// Slower C++ solution:


#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<ll,int> Pa;



struct BIT{

  int d[500005];

  int n;

 void init(int _n){

   n = _n;

   memset(d,0,sizeof(d));

 }

  // i?????????x???????????? ???1????????°?????????

  void add(int i, int x){

    while(i <= n){

      d[i] += x;

      i += i & -i;

    }

  }



  // a1??????ai?????§???????¨?????±???????

  int sum(int i){

    int s = 0;

    while(i > 0){

      s += d[i];

      i -= i & -i;

    }

    return s;

  }

};



ll N,P,Q;

BIT bit;

Pa C[500005];

int main(){

  cin >> N >> P >> Q;

  ll sum = 0;

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

    ll c; cin >> c; sum+=c;

    C[i] = Pa( (ll)(Q-i)*P - c , i );

  }

  sort( C, C + N );

  bit.init(N);

  ll res = sum;

  for(int i=N-1;i>-1;i--){

    ll p = N-1-i;

    // cout << C[i].second << endl;

    //cout << sum << " " << C[i].first << " " << p << " = " << sum + C[i].first + 2LL*p*P << endl;

    res = max( res, sum + C[i].first + 2LL*p*P );

    sum = sum + C[i].first + 2LL * p * P;

    bit.add( C[i].second+1, 1 );

  }

  cout << res << endl;

}

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

using namespace std;



typedef long long ll;

typedef pair<ll,int> Pa;



ll N,P,Q;

Pa C[500005];

int main(){

  cin >> N >> P >> Q;

  ll sum = 0;

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

    ll c; cin >> c; sum+=c;

    C[i] = Pa( (ll)(Q-i)*P - c , i );

  }

  sort( C, C + N );

  ll res = sum;

  for(int i=N-1;i>-1;i--){

    ll p = N-1-i;

    res = max( res, sum + C[i].first + 2LL*p*P );

    sum = sum + C[i].first + 2LL * p * P;

  }

  cout << res << endl;

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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

	long long N, P, Q; vector<long long> C;



	cin >> N >> P >> Q;



	C = vector<long long>(N);



	long long zenbugaishoku = 0;



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

	{

		cin >> C[i];



		zenbugaishoku += C[i];

	}

	

	vector<long long> A(N);



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

	{

		A[i] = C[i] - (Q - i) * P;

	}



	sort(A.begin(), A.end());



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



	cout << Answer << endl;



	return 0;

}

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

#include <algorithm>



using namespace std;



int main()

{

	long long P, Q, C, A[500000];



	int N;



	scanf("%d", &N);



	scanf("%lld", &P);

	scanf("%lld", &Q);



	long long zenbugaishoku = 0;



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

	{

		scanf("%lld", &C);



		zenbugaishoku += C;



		A[i] = C - (Q - i) * P;

	}



	sort(A, A + N);



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



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



	return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

	long long N, P, Q; vector<long long> C;



	scanf("%lld", &N);

	scanf("%lld", &P);

	scanf("%lld", &Q);



	C = vector<long long>(N);



	long long zenbugaishoku = 0;



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

	{

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



		zenbugaishoku += C[i];

	}

	

	vector<long long> A(N);



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

	{

		A[i] = C[i] - (Q - i) * P;

	}



	sort(A.begin(), A.end());



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



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



	return 0;

}

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

#include <algorithm>



using namespace std;



int main()

{

	long long P, Q, C, A[500000];



	int N;



	scanf("%d", &N);



	scanf("%lld", &P);

	scanf("%lld", &Q);



	long long zenbugaishoku = 0;



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

	{

		scanf("%lld", &C);



		zenbugaishoku += C;



		A[i] = C - (Q - i) * P;

	}



	sort(A, A + N);



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



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



	return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

	long long N, P, Q; vector<long long> C;



	cin >> N >> P >> Q;



	C = vector<long long>(N);



	long long zenbugaishoku = 0;



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

	{

		cin >> C[i];



		zenbugaishoku += C[i];

	}

	

	vector<long long> A(N);



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

	{

		A[i] = C[i] - (Q - i) * P;

	}



	sort(A.begin(), A.end());



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



	cout << Answer << endl;



	return 0;

}

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

#include <algorithm>



using namespace std;



int main()

{

	long long P, A[500000];



	int N, C, Q;



	scanf("%d", &N);



	scanf("%lld", &P);



	scanf("%d", &Q);



	long long zenbugaishoku = 0;



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

	{

		scanf("%d", &C);



		zenbugaishoku += C;



		A[i] = C - (Q - i) * P;

	}



	sort(A, A + N);



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



	long long V = 2 * P;



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

	{

		sum += V * i - A[i];



		Answer = max(sum, Answer);

	}



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



	return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

	long long N, P, Q; vector<long long> C;



	scanf("%lld", &N);

	scanf("%lld", &P);

	scanf("%lld", &Q);



	C = vector<long long>(N);



	long long zenbugaishoku = 0;



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

	{

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



		zenbugaishoku += C[i];

	}

	

	vector<long long> A(N);



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

	{

		A[i] = C[i] - (Q - i) * P;

	}



	sort(A.begin(), A.end());



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



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



	return 0;

}

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

#include <algorithm>



using namespace std;



int main()

{

	long long P, A[500000];



	int N, C, Q;



	scanf("%d", &N);



	scanf("%lld", &P);



	scanf("%d", &Q);



	long long zenbugaishoku = 0;



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

	{

		scanf("%d", &C);



		zenbugaishoku += C;



		A[i] = C - (Q - i) * P;

	}



	sort(A, A + N);



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



	long long V = 2 * P;



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

	{

		sum += V * i - A[i];



		Answer = max(sum, Answer);

	}



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



	return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

	long long N, P, Q; vector<long long> C;



	cin >> N >> P >> Q;



	C = vector<long long>(N);



	long long zenbugaishoku = 0;



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

	{

		cin >> C[i];



		zenbugaishoku += C[i];

	}

	

	vector<long long> A(N);



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

	{

		A[i] = C[i] - (Q - i) * P;

	}



	sort(A.begin(), A.end());



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



	cout << Answer << endl;



	return 0;

}

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

#include <algorithm>



using namespace std;



int main()

{

	long long P, C[500000];



	int N, Q;



	scanf("%d", &N);



	scanf("%lld", &P);



	scanf("%d", &Q);



	long long zenbugaishoku = 0;



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

	{

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



		zenbugaishoku += C[i];



		C[i] = C[i] - (Q - i) * P;

	}



	long long *E = C + N;



	sort(C, E);



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



	long long V = 2 * P;



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

	{

		sum += V * i - C[i];



		Answer = max(sum, Answer);

	}



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



	return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

	long long N, P, Q; vector<long long> C;



	scanf("%lld", &N);

	scanf("%lld", &P);

	scanf("%lld", &Q);



	C = vector<long long>(N);



	long long zenbugaishoku = 0;



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

	{

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



		zenbugaishoku += C[i];

	}

	

	vector<long long> A(N);



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

	{

		A[i] = C[i] - (Q - i) * P;

	}



	sort(A.begin(), A.end());



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



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



	return 0;

}

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

#include <algorithm>



using namespace std;



int main()

{

	long long P, C[500000];



	int N, Q;



	scanf("%d", &N);



	scanf("%lld", &P);



	scanf("%d", &Q);



	long long zenbugaishoku = 0;



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

	{

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



		zenbugaishoku += C[i];



		C[i] = C[i] - (Q - i) * P;

	}



	long long *E = C + N;



	sort(C, E);



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



	long long V = 2 * P;



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

	{

		sum += V * i - C[i];



		Answer = max(sum, Answer);

	}



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



	return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

	long long N, P, Q; vector<long long> C;



	cin >> N >> P >> Q;



	C = vector<long long>(N);



	long long zenbugaishoku = 0;



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

	{

		cin >> C[i];



		zenbugaishoku += C[i];

	}

	

	vector<long long> A(N);



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

	{

		A[i] = C[i] - (Q - i) * P;

	}



	sort(A.begin(), A.end());



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



	cout << Answer << endl;



	return 0;

}

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

#include <algorithm>



using namespace std;



int main()

{

	long long P, C[500000];



	int N, Q;



	scanf("%d", &N);



	scanf("%lld", &P);



	scanf("%d", &Q);



	long long zenbugaishoku = 0;



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

	{

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



		zenbugaishoku += C[i];



		C[i] = C[i] - (Q - i) * P;

	}



	long long *E = C + N;



	sort(C, E);



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



	long long V = 2 * P;



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

	{

		sum += V * i - C[i];



		Answer = max(sum, Answer);

	}



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



	return 0;

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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

	long long N, P, Q; vector<long long> C;



	scanf("%lld", &N);

	scanf("%lld", &P);

	scanf("%lld", &Q);



	C = vector<long long>(N);



	long long zenbugaishoku = 0;



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

	{

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



		zenbugaishoku += C[i];

	}

	

	vector<long long> A(N);



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

	{

		A[i] = C[i] - (Q - i) * P;

	}



	sort(A.begin(), A.end());



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



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

	{

		sum -= A[i];



		sum += 2 * i * P;



		Answer = max(sum, Answer);

	}



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



	return 0;

}

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

#include <algorithm>



using namespace std;



int main()

{

	long long P, C[500000];



	int N, Q;



	scanf("%d", &N);



	scanf("%lld", &P);



	scanf("%d", &Q);



	long long zenbugaishoku = 0;



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

	{

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



		zenbugaishoku += C[i];



		C[i] = C[i] - (Q - i) * P;

	}



	long long *E = C + N;



	sort(C, E);



	long long Answer = zenbugaishoku;



	long long sum = zenbugaishoku;



	long long V = 2 * P;



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

	{

		sum += V * i - C[i];



		Answer = max(sum, Answer);

	}



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



	return 0;

}