akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    //Int(n);
    //int n; cin >> n;
    //int2(n, k);
    Int(n); Int(k);

    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    
    vector<int> dp(n, INF);
    dp[0] = 0;

    //rep(i, n) {
    for (int i = 0; i < n; i++) {
        //Rep(j, k+1) {
        for (int j = 1; j < k+1; j++) {
            if (i + j >= n) break;
            dp[i+j] = 
                min(dp[i+j], dp[i] + abs(data[i] - data[i+j]));
        }
    }

    std::cout << dp[n-1] << std::endl;


    return 0;
}


Measured memory_bytes: 1792
/*
@author: sharrad99
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	if(n % 10 == 2 or n % 10 == 4 or n % 10 == 5 or n % 10 == 7 or n % 10 == 9) {
		cout << "hon";
	} else if(n % 10 == 0 or n % 10 == 1 or n % 10 == 6 or n % 10 == 8) {
		cout << "pon";
	} else if(n % 10 == 3) {
		cout << "bon";
	} else {
		assert(false);
	}
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;

int main() {
  long long n,k;
  long long ans = 0;
  cin >> n >> k;
  if(k == 0){
    cout << n*n << endl;
    return 0;
  }
  for(int b = k+1;b <= n;b++){
    ans += (n/b)*(b-k);
    int edge = n-(n/b)*b-k+1;
    if(edge > 0) ans += edge;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
while True:
     m=int(input())
     p=1000-m
     y500=p//500
     x500=p%500
     y100=x500//100
     x100=x500%100
     y50=x100//50
     x50=x100%50
     y10=x50//10
     x10=x50%10
     y5=x10//5
     x5=x10%5
     if m==0:
          break
     print(y500+y100+y50+y10+y5+x5)


Measured memory_bytes: 5588
from math import sqrt

X = int(input())
not_finded = True
X = X+1 if (X%2 == 0) and X != 2 else X 

def is_prime(X):
    flag = True
    for i in range(3, int(sqrt(X))+1):
        if X % i == 0:
            flag = False
    return flag

while (not_finded):
    if is_prime(X):
        not_finded = False
        print(X)
    else:
        X += 2


Measured memory_bytes: 3060
N, X = [int(x) for x in input().split()]
L = [int(x) for x in input().split()]

count = 1
d = [0] * (N+1)
for i in range(1, N+1):
    d[i] = d[i-1] + L[i-1]
    if d[i] <= X:count += 1

print(count) 

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector <long long int, long long int> 
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

ll add(ll x, ll y) {ll res=x+y; return(res>=MOD?res-MOD:res);}
ll mul(ll x, ll y) {ll res=x*y; return(res>=MOD?res%MOD:res);}
ll sub(ll x, ll y) {ll res=x-y; return(res<0?res+MOD:res);}
ll lcm(ll x, ll y) {ll res=(x*y)/__gcd(x,y); return res;}
ll power(ll x, ll y) {ll res=1; x%=MOD; while(y){if(y&1)res=mul(res,x); y>>=1; x=mul(x,x);} return res;}
const int inf = 1e9 + 5;
const ll inf64 = 1e18 + 5;

const int fix = 1e9;
int main()
{
	boost;
	int n, k, s, i;
	cin >> n >> k >> s;
	vi v;
	fo(i, 0, k)
	v.pb(s);
	fo(i, k, n)
	v.pb(s % fix + 1);
	for(auto x : v)
	cout << x << ' ';
}

Measured memory_bytes: 1912
N = int(input())
L = [0]*N    
for X in range(1,100):
    for Y in range(1,100):
        for Z in range(1,100):
            Num = X*X+Y*Y+Z*Z+X*Y+X*Z+Y*Z
            if Num>N: break
            else: L[Num-1] += 1
print('\n'.join(str(X) for X in L))

Measured memory_bytes: 9528
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, lint> pll;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 100010;

int main(){
    int n, K, s;
    while(scanf("%d%d%d", &n, &K, &s) && n){
        int ans = 0;
        rep(S, 1<<n)if(__builtin_popcount(S) == K){
            int sum = 0;
            rep(i, n)if(S>>i & 1) sum += i+1;
            if(sum == s) ++ans;
        }
        printf("%d\n", ans);
    }
}


Measured memory_bytes: 3148
#include <iostream>
#include <algorithm>
#define MAX 23

using namespace std;

int ans;
bool unreached = true;

void movestone(int counter, int d, int x, int y, int p[MAX][MAX]){

	if (counter > 10){
		return;
	}




	int temp[MAX][MAX];
	int nextx, nexty;
	nextx = x;
	nexty = y;

	//1マス移動
	if (d == 0){
		x--;
		nextx = x - 1;
	}
	else if (d == 1){
		y--;
		nexty = y - 1;
	}
	else if (d == 2){
		x++;
		nextx = x + 1;
	}
	else if (d = 3){
		y++;
		nexty = y + 1;
	}


	//ゴール判定
	if (p[y][x] == 3){
		ans = min(ans, counter);
		unreached = false;
		return;
	}


	//岩に衝突した場合
	if (p[nexty][nextx] == 1){
		for (int i = 0; i < MAX; i++){
			for (int j = 0; j < MAX; j++){
				temp[i][j] = p[i][j];
			}
		}
		temp[nexty][nextx] = 0;
		counter++;
		if (temp[y][x - 1] != 1 && temp[y][x - 1] != -1){
			movestone(counter, 0, x, y, temp);
		}
		if (temp[y - 1][x] != 1 && temp[y - 1][x] != -1){
			movestone(counter, 1, x, y, temp);
		}
		if (temp[y][x + 1] != 1 && temp[y][x + 1] != -1){
			movestone(counter, 2, x, y, temp);
		}
		if (temp[y + 1][x] != 1 && temp[y + 1][x] != -1){
			movestone(counter, 3, x, y, temp);
		}
	}

	//何もなかった場合
	else if (p[nexty][nextx] != -1){
		movestone(counter, d, x, y, p);
	}
}


int main()
{
	int w, h, startx, starty, p[MAX][MAX];
	while (cin >> w >> h, w || h){

		//初期化
		ans = 100;
		unreached = true;
		for (int i = 0; i < MAX; i++){
			for (int j = 0; j < MAX; j++){
				p[i][j] = -1;
			}
		}

		//入力
		for (int i = 1; i < h + 1; i++){
			for (int j = 1; j < w + 1; j++){
				cin >> p[i][j];
				if (p[i][j] == 2){
					startx = j;
					starty = i;
				}
			}
		}

		//移動させる
		if (p[starty][startx - 1] != 1 && p[starty][startx - 1] != -1){
			movestone(1, 0, startx, starty, p);
		}
		if (p[starty - 1][startx] != 1 && p[starty - 1][startx] != -1){
			movestone(1, 1, startx, starty, p);
		}
		if (p[starty][startx + 1] != 1 && p[starty][startx + 1] != -1){
			movestone(1, 2, startx, starty, p);
		}
		if (p[starty + 1][startx] != 1 && p[starty + 1][startx] != -1){
			movestone(1, 3, startx, starty, p);
		}

		//移動終了	
		if (unreached){
			cout << -1 << endl;
		}
		else{
			cout << ans << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1388
#include <iostream>
#include <math.h>
using namespace std;

int main() {
  int n, minv, maxv, e;
  int count = 0;
  cin >> n;

  maxv = -pow(10, 9);
  cin >> minv;
  for (int i = 1; i < n; i++) {
    cin >> e;
    maxv = max(maxv, e - minv);
    minv = min(minv, e);
  }
  cout << maxv << endl;

  return 0;
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;

int main(){
  int64_t N,A,B;
  cin>>N>>A>>B;

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

  int64_t ans=0;
  for(int i=0;i<N-1;++i){
    if(B>A*(X[i+1]-X[i])) ans += A*(X[i+1]-X[i]);
    else ans += B;
  }

  cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <complex>

using ll = long long int;
using namespace std;

int main(){
  ll X;
  cin >> X;

  ll ans = 0;
  ans = (X/500)*1000 + ((X - (X/500)*500)/5)*5;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
x = input().split()
n = int(x[0])
k = int(x[1])*2
s = [input().split() for i in range(k)]
l = []
for i in range(0, k):
  if i%2 != 0:
    for j in range(1, n+1):
      if (str(j) in s[i]) == True:
        l.append(j)
        pass
count = 0
for i in range(1, n+1):
  if (i in l) == False:
    count += 1
print(count)

Measured memory_bytes: 9512
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

n, x = map(int, input().split())
X = list(map(int, input().split()))
a = abs(X[0] - x)
for i in range(1, n):
    a = gcd(a, abs(X[i] - x))
print(a)

Measured memory_bytes: 14480
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#include <string>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")

#define DEBUG(x) cout << ">> " << #x << ": " << x << endl;
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int MOD = 1000000007;
typedef long long ll;
typedef long double ld;

int main() { _
  int n, k; cin >> n >> k;
  vector<int> v(n, 0);
  vector<vector<int> > dp(n, vector<int>(k, INT32_MAX));
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  dp[1][0] = abs(v[0] - v[1]);
  for (int i = 0; i < k; i++) dp[0][i] = 0;

  for (int i = 2; i < n; i++) {
    for (int j = 0; j < k; j++) {
      if (i - j >= 1)
        dp[i][j] = *min_element(dp[i-j-1].begin(), dp[i-j-1].end()) + abs(v[i] - v[i-j-1]);
    }
  }
  cout << *min_element(dp[n-1].begin(), dp[n-1].end()) << endl;
  return 0;
}

Measured memory_bytes: 45696
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));

console.log(main());
function main(){
  var w = o.a();
  var h = o.a();
  var n = o.a();
  var b = Array(h+1).fill(0).map(a=>{return {};});
  for(var i = 0; i < n; i++){
    var t = o.l();
    if(t[0] < t[1])continue;
    b[t[1]][t[0]] = 1;
  }
  for(i = 1; i <= h; i++)b[i][w+1] = 1;
  var ans = Object.keys(b[1])[0] - 1;
  var x = 2;
  for(i = 2; i <= h; i++){
    while(b[i][x])x++;
    if(x > ans)break;
    for(var j in b[i]){
      j = +j;
      if(x >= j)continue;
      if(j - 1 < ans)ans = j - 1;
      break;
    }
    x++;
  }
  return ans;
}

Measured memory_bytes: 101276
#include <bits/stdc++.h>
using namespace std;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

typedef long long LL;
const LL mod=1000000007;
#define MAX 10000
#define NIL -1
const double PI  = acos(-1.0);
const int INF = 1e9 + 7;
//-------------------------------------------


int main(){

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

    int a,b,c;
    cin >> a >> b >> c;

    int sum = 0;
    sum = a + b + c;
    int cnt = 0;

    while(1){
        if( sum % 3 == 0 ){
            if( sum / 3 >= a && sum / 3 >= b && sum / 3 >= c){
                goto last;
            }
        }
        sum = sum + 2;
        cnt++;
    }

    last:

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
a, b, c, x, y = map(int, input().split())
k = min(x, y)
ans = 0
if a + b >= 2 * c:
  ans += 2 * k * c
  if x >= y:
    ans += min((x - k) * a, 2 * c * (x - k))
  elif x < y:
    ans += min((y - k) * b, 2 * c * (y - k))
else:
  ans += x * a + y * b
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <bitset>
#include<vector>
#include<utility>
#include<fstream>
#include<queue>
#include <iomanip>
#include<numeric>
#include<set>
#include<map>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i,n) for(int i=0;i<n;i++)
char ca;
const int MOD = 1000000007;
ll  c = 0, d = 0, e = 0, f = 0,g=0, n, m,i, j, k, h, w, o, a[100005], b[10000] = {};
queue<ll> q;
string s[200005];
pair<ll, ll> p[20][20];

vector<int> v;
const int MAX = 2005;
long long fac[MAX], finv[MAX], inv[MAX];

int main() {
	cin >> n;
	rep(i, n)cin >> s[i];
	sort(s, s + n);
	e = 1;

	rep(i, n-1) {
		if (s[i] == s[i + 1]) {
			e++;
		}
		else {
			if (g > e) {
				e = 1;
				continue;
			}
			else if(g==e) {
				v.push_back(i);
				e = 1;
			}
			else{ 
				v.clear();
				v.push_back(i);
				g = e;
				e = 1;
			}		

		}

	}
	if (g == e) {
		v.push_back(n-1);
	}
	if(g<e) {
		v.clear();
		v.push_back(n-1);
		g = e;
	}


	rep(i,v.size()) {
		cout << s[v[i]]<<"\n";
	}

	return 0;

}

Measured memory_bytes: 15224
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
long A[99999];
void Calc(){
	int N = rei();
	for(int i=0;i<N;i++){
		A[i] = rei();
	}
	long sum = 0;
	for(int i=0;i<N;i++){
		sum += A[i];
	}
	long before = sum;
	for(int i=1;i<N;i+=2){
		before -= A[i]*2;
	}
	cout << before;
	for(int i=0;i<N-1;i++){
		before = A[i]*2-before;
		cout << " " << before;
	}
	cout << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 2176
import numpy as np
MOD = 1000000007

def solve(S, N):
    a = [0] * (2 * N)
    if S[0] == 87:
        return 0
    a[0] = 1
    for i in range(1, 2 * N):
        # L - R の回数だけひっくり返される
        if i & 1:
            if S[i] == 66:
                a[i] = a[i - 1]
                if 2 * a[i] < i + 1:
                    return 0
            else:
                a[i] = a[i - 1] + 1
        else:
            if S[i] == 87:
                a[i] = a[i - 1]
                if 2 * a[i] < i + 1:
                    return 0
            else:
                a[i] = a[i - 1] + 1
    if a[2 * N - 1] > N:
        return 0

    ans = 1
    for n in range(1, 2*N):
        if a[n] == a[n - 1]:
            ans = ans * (2 * a[n] - n) % MOD
    for n in range(2, N + 1):
        ans = ans * n % MOD
    return ans


stdin = open(0, 'rb')
N = int(stdin.readline())
S = np.frombuffer(stdin.readline(), dtype=np.int8)
# B 66 W 87
print(solve(S.tolist(), N))

Measured memory_bytes: 21828
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
int main()
{
    ll n;
    cin>>n;
    ll arr[n];
    ll sumarr[n];
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    for(int i=n-1;i>=0;i--)
    {
        if(i==n-1)
            sumarr[n-1]=arr[i];
        else
            sumarr[i]=(sumarr[i+1]+arr[i])%mod;
    }
    ll sum=0;
    for(ll i=0;i<n-1;i++)
        sum=(sum+(arr[i]*sumarr[i+1])%mod)%mod;
    cout<<sum;
    return 0;
}

Measured memory_bytes: 6744
import numpy as np
N, W = map(int, input().split())

dp=np.zeros((N+1, W+1), dtype=np.int64)

for i in range(1,N+1):
    w, v =list(map(int, input().split()))
    dp[i]=dp[i-1]
    dp[i][w:]=np.maximum(dp[i-1][:W-w+1]+v, dp[i-1][w:])
print(np.max(dp))

Measured memory_bytes: 106260
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

int64_t gcd(int64_t a, int64_t b) {
  if (a > b) {
    swap(a, b);
  }

  assert(a <= b);
  if (a == 0) {
    return b;
  }

  return gcd(b % a, a);
}

main() {
  int64_t n;
  cin >> n;

  vector<int64_t> t(n);
  for (auto&& tt : t) {
    cin >> tt;
  }

  int64_t ans = t.front();
  for (auto tt : t) {
    auto g = gcd(ans, tt);
    ans = g * (ans / g) * (tt / g);
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
///スマホコーディング
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
typedef long long ll;
const int inf=1e9;
int main(){
  int x,a,b;cin>>x>>a>>b;
  x-=a;
  int t=x/b;
  x-=t*b;
  cout<<x<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_W 100
#define MAX_H 100

int board[MAX_H + 1][MAX_W + 1];
bool ans = false;

void swapAB(int a[], int b[]);
void resetBoard();
void setBoard(int c, int d, int x, int y);
void loop(int xn, int yn, int xg, int yg, int c);
void disp(int w, int h);

int main(){
    int w, h;
    while(cin >>w >>h){
        if(w == 0 && h == 0) break;
        int xs, ys, xg, yg, n;
        resetBoard();
        ans = false;
        cin >>xs >>ys >>xg >>yg >>n;
        for(int i = 0; i < n; i++){
            int c, d, x, y;
            cin >>c >>d >>x >>y;
            setBoard(c, d, x, y);
        }
//        disp(w, h);
        if(board[ys][xs] == 0){
            cout <<"NG" <<endl;
        } else{
            loop(xs, ys, xg, yg, board[ys][xs]);
            if(ans) cout <<"OK" <<endl;
            else cout <<"NG" <<endl;
        }
    }
    return 0;
}   

void swapAB(int a[], int b[]){
    for(int i = 0; i < 8; i++){
        int tmp = a[i];
        a[i] = b[i];
        b[i] = tmp;
    }
}

void resetBoard(){
    for(int i = 0; i <= MAX_H; i++){
        for(int j = 0; j <= MAX_W; j++){
            board[i][j] = 0;
        }
    }
}

void setBoard(int c, int d, int x, int y){
    int xm[] = {0, 1, 2, 3, 0, 1, 2, 3}, ym[] = {0, 0, 0, 0, 1, 1, 1, 1};
    if(d == 1) swapAB(xm, ym);
    for(int i = 0; i < 8; i++){
        int tmpx = x + xm[i], tmpy = y + ym[i];
        if(tmpx > 0 || tmpy > 0 || tmpx <= MAX_W || tmpy <= MAX_H){
            board[tmpy][tmpx] = c;
        }
    }
}
void loop(int xn, int yn, int xg, int yg, int c){
    if(xn == xg && yn == yg){
        ans = true;
    } else{
        board[yn][xn] = 0;
        int xm[] = {0, 1, 0, -1}, ym[] = {-1, 0, 1, 0};
        for(int i = 0; i < 4; i++){
            int tmpx = xn + xm[i], tmpy = yn + ym[i];
            //            cout <<"tmpx = " <<tmpx <<", tmpy = " <<tmpy <<endl;
            if(tmpx > 0 && tmpy > 0 && tmpx <= MAX_W && tmpy <= MAX_H && board[tmpy][tmpx] == c){
                loop(tmpx, tmpy, xg, yg, c);
            }
        }
    }
}

void disp(int w, int h){
    for(int i = 0; i <= h; i++){
        for(int j = 0; j <= w; j++){
            cout <<board[i][j];
        }
        cout <<endl;
    }
}

//0, 01:15:08

Measured memory_bytes: 0
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#include<math.h>
#include<inttypes.h>
#define mprint(x) printf(FORMATCONVERSION(x),(x))
#define FORMATCONVERSION(x) _Generic((x),\
                                    int:"%d",unsigned int:"%u",\
                                    double:"%lf",long long int:"%lld",\
                                    unsigned long long int:"%llu",\
                                    unsigned long : "%lu",\
                                    long int : "%ld",\
                                    char :"%c",char*:"%s")


int main(void){

    char number_buf[102];
    scanf("%s",number_buf);
    int k;
    scanf("%d",&k);
    int dig = strlen(number_buf);
    unsigned long int dig_dp[102][/*small flag*/2][/*not 0 count*/5] = {};
    dig_dp[0][false][0] = 1;

    
    for(int i = 0;i < dig;i++){
        for(int small_flag = 0;small_flag < 2;small_flag++){
            for(int not_zero_count = 0;not_zero_count <= k;not_zero_count++){
                for(int num = 0;num <= (small_flag ? 9 : (number_buf[i] - '0'));num++)
                    dig_dp[i + 1][small_flag || num < (number_buf[i] - '0')][not_zero_count + (num != 0?1:0)] += dig_dp[i][small_flag][not_zero_count];
            }
        }
    }

    mprint(dig_dp[dig][0][k] + dig_dp[dig][1][k]);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

string S;

bool check() {
  for (ll i = 1; i < S.size(); ++i)
    if (S[i - 1] == S[i]) return false;
  return true;
}
int main() {
  cin >> S;
  cout << (check() ? "Good" : "Bad") << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.math.*;
public class Main {
	static int[] color;
	static int[] component;
	static int component_count;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long a = in.nextLong();
		long b = in.nextLong();
		long c = in.nextLong();
		long k = in.nextLong();
		long ans = a;
		long altans = 0L;
		if(a >= k) {
			ans = k;
		}else if(ans + b < k) {
			altans = ans + b;
			ans -= Math.abs(altans - k);
		}	
		System.out.println(ans);
	}
} 


Measured memory_bytes: 35808
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
// #define int long long

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
/***** MAIN *****/
signed main() {
  int n;
  cin >> n;
  vector<int> v(n);
  REP(i,n) {
    cin >> v[i];
  }
  vector<int> command;
  while(true) {
    bool erased = false;
    REPR(i,v.size()-1) {
      if(v[i] == i+1) {
        v.erase(v.begin()+i);
        command.PB(i+1);
        erased = true;
        break;
      }
    }
    if(!erased) {
      cout << -1 << endl;
      return 0;
    }
    if(v.empty()) break;
  }
  REPROBJ(itr, command) {
    cout << *itr << endl;
  }
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n],cnt,ch,ch1,ch2,ch_1;
    cnt=0;
    for (int i=0;i<n;i++){
        cin >> a[i];
        if(i==0){
            ch=a[i];
        }
        else{
            if(cnt == 0){
                if(a[i]<ch){
                    cnt+=1;
                  	//cout << i << a[i] << ch << endl;
                    if(i>1){
                        ch_1 = a[i-1];
                        ch2=1;
                    }
                    ch1 = ch;
                    ch2 = a[i];
                    ch = a[i];
                    }
                else{
                    ch=a[i];
                }
            }else if(cnt == 1){
                if(a[i]<ch){
                    if(ch2==1){
                        if(ch1<ch || ch_1>a[i]){
                            cout << "NO" << endl;
                            goto OUT;
                        }
                        else{
                            cnt+=1;
                            //cout << i << a[i] << ch  << endl;
                            ch=a[i];
                        }
                    }else{
                        if(ch1<ch){
                            cout << "NO" << endl;
                            goto OUT;
                        }
                        else{
                            cnt+=1;
                            //cout << i << a[i] << ch  << endl;
                            ch=a[i];
                        }
                    }
                }else{
                    //cnt+=1;
                  	//cout << i << a[i] << ch << endl;
                    ch=a[i];
                }
            }else if(cnt == 2){
                if(a[i]<ch){
                    cout << "NO" << endl;
                    goto OUT;
                }else{
                    //cnt+=1;
                  	//cout << i << a[i] << ch << endl;
                    ch=a[i];
                }

            }
        }
    }
    if(cnt == 0 || cnt == 2){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    OUT:
    return 0;  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
LL p = 1000000007ll;

int main(void)
{
  LL n;
  cin >> n;
  vector<LL> a(n);
  for(LL &x:a) cin >> x;
  LL answer = 1;
  LL tmp = 1;
  REP(i,n-1) {
    if((a[i]+3)/2 > tmp) ++tmp;
    answer *= tmp;
    answer %= p;
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 1024
use std::io;
use std::str::FromStr;
use std::cmp::min;

fn input<T:FromStr>() -> T {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().parse().ok().unwrap()
}

fn input_vec() -> Vec<i32> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn dp(i: usize, h_vec: &Vec<i32>, cache: &mut Vec<i32>) -> i32 {
    if i == h_vec.len() - 1 {
        return 0;
    }

    if cache[i] != -1 {
        return cache[i];
    }

    let mut res = 0i32;
    if i == h_vec.len() - 2 {
        res = dp(i+1, h_vec, cache) + (h_vec[i+1] - h_vec[i]).abs();
    } else {
        res = min(dp(i+1, h_vec, cache) + (h_vec[i+1] - h_vec[i]).abs(), dp(i+2, h_vec, cache) + (h_vec[i+2] - h_vec[i]).abs());
    }
    cache[i] = res;
    res
}

fn main() {
    let n: i32 = input();
    let h_vec = input_vec();
    let mut cache: Vec<i32> = vec![-1; n as usize];
    println!("{}", dp(0, &h_vec, &mut cache));
}


Measured memory_bytes: 8956
#include<bits/stdc++.h>
using namespace std;

using ll =  long long;
using pint =  pair<int,int>;

#define INF 99999999
#define rep(i,n) for(int (i)=0,temp=(int)(n);(i)<temp;++(i)) 
#define repi(i,start,end) for(int (i)=(start),temp=(int)(end);i<(end);++(i))
#define rfor(v,x) for(const auto& (x) : (v)) //xは値を表す
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort((v), (v)+(n))
#define vsort(v) sort((v).begin(), (v).end())
#define vfsort(v,lambda) sort(all((v)),(lambda))
#define vint vector<int>
#define vvint vector<vector<int>> //vvint v(n,vint(n))のように宣言できる
#define vin(v) rep(i,(v).size()) {cin >> (v)[i];}
//最終奥義(使うときはINFも書き換えろ!!)
//#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ctoi(char c) {return c-'0';}
//lambda式 -> [&](int x, int y){return x<y;}
//vector内の重複を削除-> v.erase(unique(all(v)),v.end());

signed main(void){
  string s;cin>>s;
  string day[7]={"SUN","MON","TUE","WED","THU","FRI","SAT"};

  rep(i,7){
    if(s==day[i]){
      cout << 7-i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main()
{
	ll n; cin >> n;
	if (n == 1) {
		cout << "Hello World" << endl;
	}
	else {
		ll a, b; cin >> a >> b;
		cout << a + b << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;

int main(){
    long long N,K,sum;
    cin >> N >> K;
    sum = 0;
    long long H[N];
    for(int i=0;i<N;i++){
        cin >> H[i];
        sum = sum + H[i];
    }
    sort(H,H+N,greater<long long>());
    if(K>N){
        sum = 0;
    }else if(K!=0){
        for(int i=0;i<K;i++){
            sum=sum-H[i];
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 1792
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int n, m;
int a[1000], b[1000], c[1000];
int g[100][100];

int main(){
  cin >> n >> m;
  rep(i, n) rep(j, n) g[i][j] = inf;
  rep(i, n) g[i][i] = 0;
  rep(i, m){
    cin >> a[i] >> b[i] >> c[i], a[i]--, b[i]--;
    g[a[i]][b[i]] = g[b[i]][a[i]] = c[i];
  }
  rep(k, n) rep(i, n) rep(j, n) chmin(g[i][j], g[i][k] + g[j][k]);
  int res = 0;
  rep(i, m) res += g[a[i]][b[i]] < c[i];
  cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

int val[10]={0,2,5,5,4,5,6,3,7,6};
int dp[100005];
int vis[20];
int main()
{
    int n,m;
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for(int i=0;i<m;i++){
        int a;
        cin>>a;
        vis[a]=1;
        for(int j=val[a];j<=n;j++){
            dp[j]=max(dp[j],dp[j-val[a]]+1);
        }
    }
    int aux = n;
    while(aux!=0){
        for(int j=9;j!=0;j--){
            if(vis[j]&&aux>=val[j]&&dp[aux-val[j]]==dp[aux]-1){
                cout<<j;
                aux-=val[j];
                break;
            }
        }
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;

long long dp[101][100001];

long long int knap(int wt[],int val[],int w,int n){
    
    for(int i=1;i<n+1;i++){
        for(int j=1;j<w+1;j++){
            if(wt[i-1]<=j){
                dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
         //   cout<<dp[i][j]<<" ";
        }
    //    cout<<endl;
    }
   
//    return dp[n+1][w+1];
}

int main() {
	// your code goes here
    for(int i=0;i<101;i++)
    dp[i][0]=0;
    for(int i=1;i<100001;i++)
    dp[0][i]=0;
	int n,w;
	cin>>n>>w;
	int wt[n],val[n];
	for(int i=0;i<n;i++)
	cin>>wt[i]>>val[i];
	
	knap(wt,val,w,n);
	cout<<dp[n][w];
	return 0;
}


Measured memory_bytes: 79104
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define rep(i,n) for(i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long LLINF=1LL<<60;
//set<int>::iterator it;



int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
	
	
	int i,j,n,k;
	string s;
	cin>>n>>k>>s;
	vector<int> v;
	
	
	int ans=0,add=2*k+1,left=0,right=0;
	int tmp=0;
	int cnt=0;
	int now=1;
	for (i = 0; i < n; i++)
	{
		if (s[i] == (char)('0' + now)) cnt++;
		else {
			v.push_back(cnt);
			now = 1 - now; //0と1を切り替える時の計算 now ^= 1;
			cnt = 1; //新しいのをカウントし始める
		}
	}
	if (cnt != 0) v.push_back(cnt);
	if (v.size() % 2 == 0) v.push_back(0);
	
//	rep(i,v.size())cout<<v[i];
	for(i=0;i<v.size();i+=2){
		int nextleft=i;
		int nextright=min(i+add,(int)v.size());
		
		while(nextleft>left){
			tmp-=v[left];
			left++;
		}
		while(nextright>right){
			tmp+=v[right];
			right++;
		}
		ans=max(tmp,ans);
//		cout<<tmp<<endl;
	}
	fin(ans);
	
	
	
	
	
	
//////////////////////////////////////////////////////
	return 0;
}


Measured memory_bytes: 1020
#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
#include<string.h>
using namespace std;
typedef long long int llint;
int main(){
	int n;
	cin >> n;
	vector<int>a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	cout << a[n - 1] - a[0] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }
// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }
//

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}

int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    // assert(i <= N);
    return i;
}
void read_cr() {
    fgets(_buf, 256, stdin);
}

vector<pair<int, int>> rle(vi& s) {
    vector<pair<int, int>> work;
    int last = -1;
    int count = 0;
    for (char c : s) {
        if (c == last) {
            ++count;
        } else {
            if (count > 0) {
                work.push_back(make_pair(last, count));
            }
            last = c; count = 1;
        }
    }
    if (count > 0) {
        work.push_back(make_pair(last, count));
    }
    return work;
}

ll solve(int N, vi& a) {
    vector<ii> b=rle(a);
    int ans = 0;
    for (ii p: b){
        ans += p.second /2;
    }
    return ans;
}

int main() {
    vi a;
    int N = loadvec(a);
    cout << solve(N,a) << endl;
    // cout << (solve(N,a) ? "Yes":"No") << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef pair<int,int> Pt;
#define fr first
#define sc second

int main(){
  int n,S;
  int ans = 0;
  while(cin >> n >> S && n){
    int vc[n];
    for(int i=0;i<n;i++) cin >> vc[i];
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
        if(vc[i] + vc[j] > S) ans++;
      }
    }
    cout << ans << endl;
    ans = 0;
  }
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
int N, Q;
int c[500005], tree[500005], last_visit[500005], ans[500005];
struct query
{
  int l;
  int r;
  int idx;
}q[500005];
int lowbit(int x)
{
  return x & -x;
}
void add(int x, int a)
{
  for (int i = x; i <= N; i += lowbit(i)) tree[i] += a;
}
int que(int x)
{
  int sum = 0;
  for (int i = x; i; i -= lowbit(i)) sum += tree[i];
  return sum;
}
bool cmp(const query &i, const query &j)
{
  return i.r < j.r;
}

int main()
{
  //memset(last_visit, -1, sizeof(last_visit));
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> N >> Q;
  for (int i = 1; i <= N; ++i) cin >> c[i];
  for (int i = 1; i <= Q; ++i)
    {
      cin >> q[i].l >> q[i].r;
      q[i].idx = i;
    }
  sort(q + 1, q + Q + 1, cmp);
  int next = 1;
  for (int i = 1; i <= Q; ++i)
    {
      for (int j = next; j <= q[i].r; ++j)
        {
          if (last_visit[c[j]]) add(last_visit[c[j]], -1);
          last_visit[c[j]] = j;
          add(j, 1);
         }
      next = q[i].r + 1;
      ans[q[i].idx]  = que(q[i].r) - que(q[i].l - 1);
    }
  for (int i = 1; i <= Q; ++i) cout << ans[i] << endl;
  return 0;
}
/*
#include<iostream>
#include<cmath>
#include<algorithm>

#define ll long long

using namespace std;

const int N = 1e6 + 10;

int tr[N];
int n,m;
int last[N];
int ans[N];
struct node{
        int l,r,pos;
}nod[N];

int color[N];

int lowbit(int x)
{
        return x & -x;
}

void add(int x, int a)
{
        for(int i=x; i<=n; i+=lowbit(i)) tr[i]+=a;
}

int query(int x)
{
        int rul = 0;
        for(int i=x; i; i-=lowbit(i)) rul += tr[i];
        return rul;
}

bool cmp(node a, node b)
{
        return a.r < b.r;
}

int main()
{
        cin>>n>>m;
        for(int i=1; i<=n; i++) scanf("%d",&color[i]);
        for(int i=1; i<=m; i++)
        {
                scanf("%d %d",&nod[i].l,&nod[i].r);
                nod[i].pos = i;
        }
        sort(nod+1, nod+m+1, cmp);
        int next = 1;
        for(int i=1; i<=m; i++)
        {
                for(int j=next; j<=nod[i].r; j++)
                {
                        if(last[color[j]]) add(last[color[j]], -1);
                        last[color[j]] = j;
                        add(j, 1);
                }
                next = nod[i].r+1;
                ans[nod[i].pos] = query(nod[i].r) - query(nod[i].l-1);
        }
        for(int i=1; i<=m; i++)
        {
                cout<<ans[i]<<endl;
        }
        return 0;
}
*/


Measured memory_bytes: 17372
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int n;
vector<ll> a(200000);
vector<ll> s(200001); // iまでの累積和
const int MOD = 1e9 + 7;

int main() {
  cin >> n;
  s[0] = 0;
  for (int i=0; i<n; i++) {
    cin >> a[i];
    s[i+1] = (s[i] + a[i]);
  }
  
  long long ans = 0;
  for (int i = 0; i < n-1; i++) {
    long long sum = s[n] - s[i+1];
    sum %= MOD;
    ans += (a[i] * sum) % MOD;
  }
  
  cout << ans % MOD << endl;
}

Measured memory_bytes: 5776
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>


#define i_cin(X) scanf("%d", &X)
#define i_cin2(X,Y) scanf("%d %d",&X,&Y)
#define i_cin3(X,Y,Z) scanf("%d %d %d",&X,&Y,&Z)
#define l_cin(X) scanf("%ld",&X)
#define f_cin(X) scanf("%f",&X)
#define l_cin2(X,Y) scanf("%ld %ld",&X,&Y)
#define s_cin(X) scanf("%s",&X)

#define  i_cout(X) printf("%d\n",X)
#define  f_cout(X) printf("%g\n",X)
#define  i_cout2(X,Y) printf("%d %d\n",X,Y)
#define  l_cout(X) printf("%ld\n",X)
#define  s_cout(X) printf("%s\n",X)
#define  ll_cout(X) printf("%lld\n",X)

typedef long long  ll;
#define rept(x, s, n) for (int x = s; x < n; x++)

#define Yes_RTN s_cout("Yes");return 0
#define No_RTN  s_cout("No");return 0
#define YES_RTN s_cout("YES");return 0
#define NO_RTN  s_cout("NO");return 0


int i_cins(int n, int* A);
int l_cins2(int n, long* A,long* B);
int s_dsort(const void* a, const void* b);
int s_asort(const void* a, const void* b);

int  _gcd(int a, int b);


int main(void) {

	int    N,K,i,sum=0;
	int    x[100];

	i_cin2(N,K);
	i_cins(N, x);
	rept(i, 0, N) {
		if (x[i] < abs(K - x[i])) sum += x[i];
		else sum += abs(K - x[i]);
	}
	i_cout(sum*2); return 0;	
}
	

int s_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int s_asort(const void* a, const void* b) {
	return(*(int*)a -*(int*)b);
}
int l_cins2(int n, long* a, long* b) {
	int i;
	rept(i, 0, n) {
		l_cin2(*(a + i), *(b + i));
	}
	return 0;
}
int i_cins(int n, int* a) {
	int i;
	rept(i, 0, n) {
		i_cin(*(a + i));
	}

	return 0;
}

int _gcd(int a, int b) {
	int r, tmp;
	if (a < b) { tmp = a; a = b; b = tmp; }
	r = a % b;
	while (r) {
		if (!r) break;
		a = b; b = r;
		r = a % b;
	}
	return(b);
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cout << (*begin) << " ";
    *begin++;
  }
  cout << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cout << " " << Array[i][j];
    }
    cout << endl;
  }
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

// ------------------------------------------------------------------------------------------

int N, Q;
string s;
int A[111111];
int B[111111];
int dp[111111][3];

signed main() {
  cin >> N >> Q;
  cin >> s;
  int n = s.size();

  for (int i = 0; i < n-1; i++) {
    if (s[i] == 'A' and s[i+1] == 'C') {
      A[i+1] = A[i] + 1;
      A[i+2] = A[i] + 1;
    } else {
      A[i+1] = A[i];
      A[i+2] = A[i];
    }
  }
  // print1(A, A+N+1);

  while (Q--) {
    int l, r;
    cin >> l >> r;
    // dbg2(A[r], A[l])
    cout << A[r-1] - A[l-1] << endl;
  }

  return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

ll dp[100];

int main() {
    int n; cin >> n;
    dp[0] = 2; dp[1] = 1;
    for (int i = 2; i < 100; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 256