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

using namespace std;

#define LL long long

const int N = 2e5 + 10;

int n, c[N], cnt[N], siz[N];

	inline LL cal(int n) {

		// C(n,2) + n

		return 1LL*n*(n+1)/2;

	}

LL ans[N];

vector<int>G[N];

	void dfs(int v, int fa) {

		int tmp = cnt[c[v]];

		siz[v] = 1;

		for(int u:G[v]) {

			if(u==fa) continue;

			cnt[c[v]] = 0;

			dfs(u, v);

			siz[v] += siz[u];

			ans[c[v]]+=cal(siz[u]-cnt[c[v]]);

		}

		cnt[c[v]] = tmp + siz[v];

	}

int main() {

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

	std::ios::sync_with_stdio(false);

	cin>>n;

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

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

		cin>>c[i];

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

		int u, v;

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

		cin>>u>>v;

		G[u].push_back(v);

		G[v].push_back(u);

	}

	dfs(1, 0);

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

		cout<< cal(n) - ans[i] - cal(n - cnt[i])<<endl;

	}

	return 0;

}


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


#include<iostream>

#include<vector>

using namespace std;

#define LL	long long

const int MAXN = 2e5+10;



int N;

int c[MAXN];

//vector<int> G[MAXN];

int tot = 0;

int head[MAXN], Next[2*MAXN], to[2*MAXN];



// 

// sub[i]: 顶点i下子树顶点的个数

int sub[MAXN];

// cnt[i]: 颜色为i的顶点下子树顶点的个数

int cnt[MAXN]; 

// ans[i]: 颜色为i的顶点下不经过颜色i的顶点数

LL ans[MAXN];



// 一开始起名count结果和c++ count()冲突，调试了半天, md

inline LL count(int n) {

	// C(n,2) + n

	return 1LL*n*(n+1)/2;

}



void dfs(int v, int fa) {

	int tmp = cnt[c[v]];

	sub[v] = 1;

	for(int i=head[v]; i; i=Next[i]) {

		int u = to[i];

		if(u == fa) continue;

		cnt[c[v]] = 0;	// 置0重新计数

		dfs(u, v);

		sub[v] += sub[u];

		ans[c[v]] += count(sub[u] - cnt[c[v]]);

	}

	cnt[c[v]] = tmp + sub[v];

}

inline void add(int a, int b) {

	++tot;

	Next[tot] = head[a];

	to[tot] = b;

	head[a] = tot;

}



/*

void dfs(int v, int fa) {

	int tmp = cnt[c[v]];

	sub[v] = 1;

	for(int u:G[v]) {

		if(u==fa) continue;

		cnt[c[v]] = 0;

		dfs(u, v);

		sub[v] += sub[u];

		ans[c[v]]+=cal(sub[u]-cnt[c[v]]);

	}

	cnt[c[v]] = tmp + sub[v];

}

* */



int main() {

	std::ios::sync_with_stdio(false);

	cin>>N;

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

		cin >> c[i];

	}

	int a, b;

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

		cin>>a>>b;

	

		add(a, b);

		add(b, a);

		

		//G[a].push_back(b);

		//G[b].push_back(a);

	}



	//dfs1(1, 0);

	dfs(1, 0);

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

		cout << count(N) - ans[i] - count(N-cnt[i]) << endl;

	}

	return 0;

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

	#include<vector>

	using namespace std;

	#define LL	long long

	const int MAXN = 2e5+10;



	int N;

	int c[MAXN];

	vector<int> G[MAXN];

//	int tot = 0;

//	int head[MAXN], Next[MAXN], to[MAXN];



	// sub[i]: 顶点i下子树顶点的个数

	int sub[MAXN];

	// cnt[i]: 颜色为i的顶点下子树顶点的个数

	int cnt[MAXN]; 

	// ans[i]: 颜色为i的顶点下不经过颜色i的顶点数

	LL ans[MAXN];

	

	// 一开始起名count结果和c++ count()冲突，调试了半天, md

	inline LL cal(int n) {

		// C(n,2) + n

		return 1LL*n*(n+1)/2;

	}

	/*

	void dfs(int v, int fa) {

		int tmp = cnt[c[v]];

		sub[v] = 1;

		for(int i=head[v]; i; i=Next[i]) {

			int u = to[i];

			if(u == fa) continue;

			cnt[c[v]] = 0;	// 置0重新计数

			dfs(u, v);

			sub[v] += sub[u];

			ans[c[v]] += count(sub[u] - cnt[c[v]]);

		}

		cnt[c[v]] = tmp + sub[v];

	}

	void add(int a, int b) {

		++tot;

		Next[tot] = head[a];

		to[tot] = b;

		head[a] = tot;

	}

	*/

	void dfs(int v, int fa) {

		int tmp = cnt[c[v]];

		sub[v] = 1;

		for(int u:G[v]) {

			if(u==fa) continue;

			cnt[c[v]] = 0;

			dfs(u, v);

			sub[v] += sub[u];

			ans[c[v]]+=cal(sub[u]-cnt[c[v]]);

		}

		cnt[c[v]] = tmp + sub[v];

	}

	

	int main() {

		std::ios::sync_with_stdio(false);

		cin>>N;

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

			cin >> c[i];

		}

		int a, b;

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

			cin>>a>>b;

			G[a].push_back(b);

			G[b].push_back(a);

		}

		//dfs1(1, 0);

		dfs(1, 0);

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

			cout << cal(N) - ans[i] - cal(N-cnt[i]) << endl;

		}

		return 0;

	}


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


#include<iostream>

#include<vector>

using namespace std;

#define LL	long long

const int MAXN = 2e5+10;



int N;

int c[MAXN];

//vector<int> G[MAXN];

int tot = 0;

int head[MAXN], Next[2*MAXN], to[2*MAXN];



// 

// sub[i]: 顶点i下子树顶点的个数

int sub[MAXN];

// cnt[i]: 颜色为i的顶点下子树顶点的个数

int cnt[MAXN]; 

// ans[i]: 颜色为i的顶点下不经过颜色i的顶点数

LL ans[MAXN];



// 一开始起名count结果和c++ count()冲突，调试了半天, md

inline LL count(int n) {

	// C(n,2) + n

	return 1LL*n*(n+1)/2;

}



void dfs(int v, int fa) {

	int tmp = cnt[c[v]];

	sub[v] = 1;

	for(int i=head[v]; i; i=Next[i]) {

		int u = to[i];

		if(u == fa) continue;

		cnt[c[v]] = 0;	// 置0重新计数

		dfs(u, v);

		sub[v] += sub[u];

		ans[c[v]] += count(sub[u] - cnt[c[v]]);

	}

	cnt[c[v]] = tmp + sub[v];

}

inline void add(int a, int b) {

	++tot;

	Next[tot] = head[a];

	to[tot] = b;

	head[a] = tot;

}



/*

void dfs(int v, int fa) {

	int tmp = cnt[c[v]];

	sub[v] = 1;

	for(int u:G[v]) {

		if(u==fa) continue;

		cnt[c[v]] = 0;

		dfs(u, v);

		sub[v] += sub[u];

		ans[c[v]]+=cal(sub[u]-cnt[c[v]]);

	}

	cnt[c[v]] = tmp + sub[v];

}

* */



int main() {

	std::ios::sync_with_stdio(false);

	cin>>N;

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

		cin >> c[i];

	}

	int a, b;

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

		cin>>a>>b;

	

		add(a, b);

		add(b, a);

		

		//G[a].push_back(b);

		//G[b].push_back(a);

	}



	//dfs1(1, 0);

	dfs(1, 0);

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

		cout << count(N) - ans[i] - count(N-cnt[i]) << endl;

	}

	return 0;

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

using namespace std;

#define LL long long

const int N = 2e5 + 10;

int n, c[N], cnt[N], siz[N];

	inline LL cal(int n) {

		// C(n,2) + n

		return 1LL*n*(n+1)/2;

	}

LL ans[N];

vector<int>G[N];

	void dfs(int v, int fa) {

		int tmp = cnt[c[v]];

		siz[v] = 1;

		for(int u:G[v]) {

			if(u==fa) continue;

			cnt[c[v]] = 0;

			dfs(u, v);

			siz[v] += siz[u];

			ans[c[v]]+=cal(siz[u]-cnt[c[v]]);

		}

		cnt[c[v]] = tmp + siz[v];

	}

	

	inline void add(int a, int b) {

		G[a].push_back(b);

		G[b].push_back(a);

	}

	

int main() {

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

	std::ios::sync_with_stdio(false);

	cin>>n;

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

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

		cin>>c[i];

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

		int u, v;

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

		cin>>u>>v;

		G[u].push_back(v);

		G[v].push_back(u);

		//add(u, v); add(v, u);

	}

	dfs(1, 0);

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

		cout<< cal(n) - ans[i] - cal(n - cnt[i])<<endl;

	}

	return 0;

}


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


#include<iostream>

#include<vector>

using namespace std;

#define LL	long long

const int MAXN = 2e5+10;



int N;

int c[MAXN];

//vector<int> G[MAXN];

int tot = 0;

int head[MAXN], Next[2*MAXN], to[2*MAXN];



// 

// sub[i]: 顶点i下子树顶点的个数

int sub[MAXN];

// cnt[i]: 颜色为i的顶点下子树顶点的个数

int cnt[MAXN]; 

// ans[i]: 颜色为i的顶点下不经过颜色i的顶点数

LL ans[MAXN];



// 一开始起名count结果和c++ count()冲突，调试了半天, md

inline LL count(int n) {

	// C(n,2) + n

	return 1LL*n*(n+1)/2;

}



void dfs(int v, int fa) {

	int tmp = cnt[c[v]];

	sub[v] = 1;

	for(int i=head[v]; i; i=Next[i]) {

		int u = to[i];

		if(u == fa) continue;

		cnt[c[v]] = 0;	// 置0重新计数

		dfs(u, v);

		sub[v] += sub[u];

		ans[c[v]] += count(sub[u] - cnt[c[v]]);

	}

	cnt[c[v]] = tmp + sub[v];

}

inline void add(int a, int b) {

	++tot;

	Next[tot] = head[a];

	to[tot] = b;

	head[a] = tot;

}



/*

void dfs(int v, int fa) {

	int tmp = cnt[c[v]];

	sub[v] = 1;

	for(int u:G[v]) {

		if(u==fa) continue;

		cnt[c[v]] = 0;

		dfs(u, v);

		sub[v] += sub[u];

		ans[c[v]]+=cal(sub[u]-cnt[c[v]]);

	}

	cnt[c[v]] = tmp + sub[v];

}

* */



int main() {

	std::ios::sync_with_stdio(false);

	cin>>N;

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

		cin >> c[i];

	}

	int a, b;

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

		cin>>a>>b;

	

		add(a, b);

		add(b, a);

		

		//G[a].push_back(b);

		//G[b].push_back(a);

	}



	//dfs1(1, 0);

	dfs(1, 0);

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

		cout << count(N) - ans[i] - count(N-cnt[i]) << endl;

	}

	return 0;

}
// Slower C++ solution:
#define _USE_MATH_DEFINES

#include <cassert>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

#include <sstream>

#include <vector>

#include <queue>

#include <stack>

#include <list>

#include <set>

#include <map>

#include <unordered_set>

#include <unordered_map>

#include <algorithm>

#include <complex>

#include <cmath>

#include <numeric>

#include <bitset>



using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1){

  cerr << name << ": " << arg1 << endl;

}

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args){

  const char* comma = strchr(names + 1, ',');

  cerr.write(names, comma - names) << ": " << arg1 << " |";

  __f(comma + 1, args...);

}



typedef long long int64;

typedef pair<int, int> ii;

const int INF = 1 << 30;

const int MOD = 1e9 + 7;



struct Frac {

  int64 p, q;

};



Frac operator -(const Frac& a, const Frac& b) {

  int64 p = a.p * b.q - a.q * b.p;

  int64 q = a.q * b.q;

  int64 d = abs(__gcd(p, q));

  p /= d; q /= d;

  return Frac{p, q};

}



int main() {

  int n;

  cin >> n;

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

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

      auto cur = Frac{4, n} - Frac{1, i} - Frac{1, j};

      if (cur.p == 1) {

        cout << i << " " << j << " " << cur.q << endl;

        return 0;

      }

    }

  }

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.315877969701971x):
#define _USE_MATH_DEFINES

#include <cassert>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

#include <sstream>

#include <vector>

#include <queue>

#include <stack>

#include <list>

#include <set>

#include <map>

#include <unordered_set>

#include <unordered_map>

#include <algorithm>

#include <complex>

#include <cmath>

#include <numeric>

#include <bitset>



using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1){

  cerr << name << ": " << arg1 << endl;

}

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args){

  const char* comma = strchr(names + 1, ',');

  cerr.write(names, comma - names) << ": " << arg1 << " |";

  __f(comma + 1, args...);

}



typedef long long int64;

typedef pair<int, int> ii;

const int INF = 1 << 30;

const int MOD = 1e9 + 7;



struct Frac {

  int64 p, q;

};



Frac operator -(const Frac& a, const Frac& b) {

  int64 p = a.p * b.q - a.q * b.p;

  int64 q = a.q * b.q;

  int64 d = abs(__gcd(p, q));

  p /= d; q /= d;

  return Frac{p, q};

}



int main() {

  int n;

  cin >> n;

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

    auto cur = Frac{4, n} - Frac{1, i};

    for (int j = cur.q / cur.p + 1; j <= 3500; ++j) {

      auto cur = Frac{4, n} - Frac{1, i} - Frac{1, j};

      if (cur.p == 1) {

        cout << i << " " << j << " " << cur.q << endl;

        return 0;

      }

    }

  }

  return 0;

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



using namespace std;

using ll = long long;



int main(int argc, const char *argv[]) {

  int n;

  cin >> n;



  ll h = 0, nn = 0, w = 0;

  for (ll i = 1; i <= 3500 && h == 0; ++i) {

    for (ll j = 1; j <= 3500 && h == 0; ++j) {

      ll l = lcm(n, lcm(i, j));

      ll m = 4ll * (l / n) - (l / i + l / j);

      if (m <= 0) {

        continue;

      }



      if (l % m != 0) {

        continue;

      }



      h = i;

      nn = j;

      w = l / m;

    }

  }



  cout << h << ' ' << nn << ' ' << w << '\n';

}

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

#include <numeric>



using namespace std;

using ll = long long;



int main(int argc, const char *argv[]) {

  int n;

  cin >> n;



  ll h = 0, nn = 0, w = 0;

  for (ll i = 1; i <= 3500 && h == 0; ++i) {

    for (ll j = 1; j <= 3500 && h == 0; ++j) {

      ll l = n * i * j;

      ll m = 4ll * (l / n) - (l / i + l / j);

      if (m <= 0) {

        continue;

      }



      if (l % m != 0) {

        continue;

      }



      h = i;

      nn = j;

      w = l / m;

    }

  }



  cout << h << ' ' << nn << ' ' << w << '\n';

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



#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



#define sf scanf

#define pf printf

#define pb push_back

#define mp make_pair

#define PI ( acos(-1.0) )

#define mod 998244353LL

#define IN freopen("C.in","r",stdin)

#define OUT freopen("output.txt","w",stdout)

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

#define DBG pf("Hi\n")

#define INF 1000000000

#define i64 long long int

#define eps (1e-8)

#define xx first

#define yy second

#define ln 17

#define off 2



using namespace __gnu_pbds;

using namespace std ;



typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

typedef pair<i64, i64> pii;



#define maxn 300005



map<int,int> Map ;



int a[maxn] ;



int main()

{

    int n , k ;



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



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



    Map[0] = 1 ;



    i64 ans = 0 ;



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

    {

        if( i-k >= 0 )

        {

            int val = ( (a[i-k] - (i-k) )%k + k )%k ;

            Map[ val ] = Map[val] - 1 ;

        }

        a[i] = ( a[i-1] + a[i] )%k ;

        int val = ( (a[i] - i)%k + k )%k ;



        if( Map.find( val ) == Map.end() ) Map[val] = 0 ;

        ans += Map[val] ;

        Map[val] = Map[val] +  1 ;

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

    }



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



    return 0 ;

}


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

#include<algorithm>

using namespace std;

struct node{

	int b,num;

}q[200010];

long long a[200010];

int cmp(const node&x,const node&y)

{

	if(x.b!=y.b)

	 return x.b<y.b;

	return x.num<y.num;

}

int main()

{

	int n,i,l;

	long long k,ans=0;

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

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

	 {

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

	 	a[i]+=a[i-1];

	 	q[i].b=(((a[i]-i)%k)+k)%k;

	 	q[i].num=i;

	 }

	sort(q+1,q+n+1,cmp);

	l=0;

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

	 if(q[i].b==q[i-1].b)

	  {

	  		while(q[i].num-q[l].num>=k)

	  		 l++;

	  		ans+=i-l;

	  }

	else

	 l=i;

	printf("%lld",ans);

	return 0;

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

#define ll long long

using namespace std;



int main() {

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

	int n, k;

	cin>>n>>k;

	vector<ll> a(n+1), pref(n+1);

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

		cin>>a[i];

		pref[i]=(pref[i-1]+a[i])%k;

	}

	map<ll, ll> cnt;

	ll ans=0;

	cnt[0]=1;

	if(k==1) {

		cout<<0;

		return 0;

	}

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

		if(i>=k) {

			cnt[(pref[i-k]-i%k+k)%k]--;

		}

		ans += cnt[(pref[i]-i%k+k)%k];

		cnt[(pref[i]-i%k+k)%k]++;

	}

	cout<<ans;

}


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

#include<algorithm>

using namespace std;

struct node{

	int b,num;

}q[200010];

long long a[200010];

int cmp(const node&x,const node&y)

{

	if(x.b!=y.b)

	 return x.b<y.b;

	return x.num<y.num;

}

int main()

{

	int n,i,l;

	long long k,ans=0;

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

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

	 {

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

	 	a[i]+=a[i-1];

	 	q[i].b=(((a[i]-i)%k)+k)%k;

	 	q[i].num=i;

	 }

	sort(q+1,q+n+1,cmp);

	l=0;

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

	 if(q[i].b==q[i-1].b)

	  {

	  		while(q[i].num-q[l].num>=k)

	  		 l++;

	  		ans+=i-l;

	  }

	else

	 l=i;

	printf("%lld",ans);

	return 0;

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

using namespace std;

typedef long long LL;

const int maxn = 200000+10;



int n,k;

int a[maxn],sum[maxn],b[maxn];

map<int,int> cnt;



int main()

{

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

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

    for (int i=1;i<=n;i++) sum[i]=(sum[i-1]+a[i])%k;

    for (int i=1;i<=n;i++) b[i]=((sum[i]-i)%k+k)%k;

    //for (int i=0;i<=n;i++) printf("%d ",b[i]); printf("\n");

    cnt[0]++;

    LL ans=0; int pre=0;

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

    {

        while (i-pre>=k)

        {

            cnt[b[pre]]--;

            pre++;

        }

        ans+=cnt[b[i]];

        cnt[b[i]]++;

    }

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

    return 0;

}


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

#include<algorithm>

using namespace std;

struct node{

	int b,num;

}q[200010];

long long a[200010];

int cmp(const node&x,const node&y)

{

	if(x.b!=y.b)

	 return x.b<y.b;

	return x.num<y.num;

}

int main()

{

	int n,i,l;

	long long k,ans=0;

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

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

	 {

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

	 	a[i]+=a[i-1];

	 	q[i].b=(((a[i]-i)%k)+k)%k;

	 	q[i].num=i;

	 }

	sort(q+1,q+n+1,cmp);

	l=0;

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

	 if(q[i].b==q[i-1].b)

	  {

	  		while(q[i].num-q[l].num>=k)

	  		 l++;

	  		ans+=i-l;

	  }

	else

	 l=i;

	printf("%lld",ans);

	return 0;

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

#include<cstdio>

#include<cstdlib>

#include<vector>

#include<cmath>

#include<algorithm>

#include<iomanip>

#include<cctype>

#include<queue>

#include<map>

#include<stack>

#include<string>

#include<cstring>

#include<set>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pii;

typedef vector<pii> vpi;

#define mp make_pair

#define pb push_back



int a[200200],n,s[200200];

int k;

map<int,int> m;

vi b[200200];



int main(){

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

	s[0]=0;

	int cnt=1;

	m.clear();

	m[0]=1;

	b[1].pb(0);

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

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

		a[i]--;

		a[i]%=k;

		s[i]=(s[i-1]+a[i])%k;

		if (m.find(s[i])==m.end()) m[s[i]]=++cnt;

		b[m[s[i]]].pb(i);

	}

	ll ans=0;

	for (map<int,int>::iterator it=m.begin();it!=m.end();it++){

		int p=it->second;

		int sz=b[p].size();

		if (sz==1) continue;

		int i=0,j=1;

		while (j<sz){

			if (b[p][j]-b[p][i]>=k) i++;

			else{

				ans+=(ll)j-i;

				j++;

			}

		}

	}

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

	return 0;

}

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



using namespace std;

 

typedef long long ll;

#define For(i,x,y) for(int i=x; i<y; ++i)

#define mem(x,y) memset(x,y,sizeof(x))

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

#define PII pair<int,int>

#define INF 0x3f3f3f3f

#define DOF 0x7f7f7f7f

#define se second

#define fi first

#define endl '\n'

 

template <typename T>

inline void read(T &r){

    static char c; r=0; int f=1;

    for(c=getchar(); c<'0'||c>'9'; c=getchar()) if(c=='-')f=-1;

    for(; c>='0'&&c<='9'; r=(r<<1)+(r<<3)+(c^48),c=getchar());

    r*=f;

} // -_-



const int N = 2e5 + 105;

ll a[N], pre[N], k;

int main(){

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

    scanf("%lld", &k);

    pre[0] = 0;

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

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

        pre[i] = pre[i - 1] + a[i];

    }

    map<ll, int>ma;

    ll ans = 0;

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

        if(i >= k){

            ma[(pre[i - k] - (i - k))%k] --;

        }

        if(ma[(pre[i] - i)%k]){

            ans += ma[(pre[i] - i)%k];

        }

        ma[(pre[i] - i)%k] ++;

    }

    cout<<ans<<endl;

    // system("pause");

    return 0;

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

#include<cstdio>

#include<cstdlib>

#include<vector>

#include<cmath>

#include<algorithm>

#include<iomanip>

#include<cctype>

#include<queue>

#include<map>

#include<stack>

#include<string>

#include<cstring>

#include<set>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pii;

typedef vector<pii> vpi;

#define mp make_pair

#define pb push_back



int a[200200],n,s[200200];

int k;

map<int,int> m;

vi b[200200];



int main(){

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

	s[0]=0;

	int cnt=1;

	m.clear();

	m[0]=1;

	b[1].pb(0);

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

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

		a[i]--;

		a[i]%=k;

		s[i]=(s[i-1]+a[i])%k;

		if (m.find(s[i])==m.end()) m[s[i]]=++cnt;

		b[m[s[i]]].pb(i);

	}

	ll ans=0;

	for (map<int,int>::iterator it=m.begin();it!=m.end();it++){

		int p=it->second;

		int sz=b[p].size();

		if (sz==1) continue;

		int i=0,j=1;

		while (j<sz){

			if (b[p][j]-b[p][i]>=k) i++;

			else{

				ans+=(ll)j-i;

				j++;

			}

		}

	}

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

	return 0;

}

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

#include<algorithm>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include<map>

#include<set>

#include<sstream>

#define INF 0x3f3f3f3f

#define DOF 0x7f7f7f7f

#define mem(a,b) memset(a,b,sizeof(a))

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long ll;

using namespace std;

const int maxn=2e5+10;

ll a[maxn],sum[maxn];

map<unsigned int,ll>num;

ll ans;

int main()

{

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

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

        cin>>a[i];

        sum[i]=sum[i-1]+a[i];

    }

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

        if(i>=k){

            num[((sum[i-k]-(i-k))%k)]--;

        }

        if(num[(sum[i]-i)%k]){

            ans+=num[(sum[i]-i)%k];

        }

        num[(sum[i]-i)%k]++;

    }

    cout<<ans<<endl;

    return 0;

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

#include<cstdio>

#include<cstdlib>

#include<vector>

#include<cmath>

#include<algorithm>

#include<iomanip>

#include<cctype>

#include<queue>

#include<map>

#include<stack>

#include<string>

#include<cstring>

#include<set>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pii;

typedef vector<pii> vpi;

#define mp make_pair

#define pb push_back



int a[200200],n,s[200200];

int k;

map<int,int> m;

vi b[200200];



int main(){

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

	s[0]=0;

	int cnt=1;

	m.clear();

	m[0]=1;

	b[1].pb(0);

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

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

		a[i]--;

		a[i]%=k;

		s[i]=(s[i-1]+a[i])%k;

		if (m.find(s[i])==m.end()) m[s[i]]=++cnt;

		b[m[s[i]]].pb(i);

	}

	ll ans=0;

	for (map<int,int>::iterator it=m.begin();it!=m.end();it++){

		int p=it->second;

		int sz=b[p].size();

		if (sz==1) continue;

		int i=0,j=1;

		while (j<sz){

			if (b[p][j]-b[p][i]>=k) i++;

			else{

				ans+=(ll)j-i;

				j++;

			}

		}

	}

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

	return 0;

}

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

using namespace std;



using ll = long long;

using ld= long double;

using ull= unsigned long long;

#define endl "\n"



const ll maxn=3e5+100;



const ll maxx=1e13;

const ll mod=1000000007;





map<ll,ll> mp;

ll f[maxn];

ll a[maxn];

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

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

   ll n, k;

   cin>>n>>k;

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

   {

       cin>>a[i];

       a[i]=a[i]-1+k;

       a[i]%=k;

   }

   f[0]=0;

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

   {

      f[i]=(f[i-1]+a[i])%k;

   }

   /*for (int i=1;i<=n;i++) cout <<f[i]<<" ";

   cout <<endl;*/

   ll kq=0;

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

   {

       ll t=i-k;

       if (t>0)

       {

           mp[f[t]]--;

       }

       if (f[i]==0)

       {

           kq=kq+mp[0];

           if (i<k) kq++;



       }

       else

       {

           kq=kq+mp[f[i]];

       }

       mp[f[i]]++;

   }

   cout << kq;

}