akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
//#include <boost/multiprecision/cpp_int.hpp>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <sstream>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
// namespace mp = boost::multiprecision;
using namespace std;
using ull = unsigned long long;
using ld = long double;
// using ll = boost::multiprecision::cpp_int;
using ll = long long;
#define FOR(i, N) for(ll i = 0; i < N; ++i)

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
// using int = ll;
ll gcd(ll m, ll n) {
    if(n == 0)
        return abs(m);
    return (gcd(n, m % n));
}
void putYN(bool b) {
    if(b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
void swap(ll &a, ll &b) {
    ll tmp = a;
    a = b;
    b = tmp;
}
ll combi(ll n, ll k) {
    ll r = 1, rr = 1;
    for(ll i = 0; i < k; ++i) {
        r *= (n - i);
        rr *= (i + 1);
        // r %= 1000000007;
        // rr %= 1000000007;
    }
    r /= rr;
    // r %= 1000000007;
    return r;
}
int main() {
    string s, t;
    cin >> s >> t;
    map<char, vector<ll>> nummap;
    FOR(i, s.size()) {
        ;
        if(nummap.find(s[i]) == nummap.end()) {
            nummap[s[i]] = vector<ll>();
        }
        auto itr = lower_bound(nummap[s[i]].begin(), nummap[s[i]].end(), i);
        nummap[s[i]].insert(itr,i);
    }
    /*for(auto a : nummap) {
        sort(a.second.begin(), a.second.end());
    }*/
    FOR(i, t.size()) {
        if(nummap.find(t[i]) == nummap.end()) {
            cout << -1 << endl;
            return 0;
        }
    }
    ll min_ = LLONG_MAX;
    //for(ll ii = 0; ii < nummap[t[t.size() - 1]].size(); ++ii) {
    {
        ll re = 0;
        //ll num = nummap[t[t.size() - 1]][ii];
        ll num = -1;
        for(ll i = 0; i<t.size(); ++i) {
            vector<ll> &v = nummap[t[i]];
            auto numi = lower_bound(v.begin(), v.end(), num+1);

            // cout << *(numi - 1) << " " << num << endl;
            if(numi == v.end()) {
                re++;
                num = v[0];
            } else {
                //cout << num << *(numi)<<endl;
                num = *(numi);
            }
        }
        ll m = re * s.size() + num + 1;
        if(m < min_)
            min_ = m;
    }
    cout << min_ << endl;
    return 0;
}


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

using namespace std;
#define ll long long

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    char ch;
    cin>>ch;

    if((ch >= 'A') &&( ch <='Z'))
        cout<<"A"<<endl;
    else
        cout<<'a'<<endl;

    return 0;
}


Measured memory_bytes: 3660
cardTypeList = ['S', 'H', 'C', 'D']
havingCardList = []
for i in range(0, int(input())):
    cardType, num = list(input().split())
    havingCardList.append([cardType, int(num)])

# 全体を確認して　持っているリストになかったら表示用リストに追加
displayList = []
for i in cardTypeList:
    for j in range(1, 13 + 1):
        compareList = [i, j]
        if compareList not in havingCardList:
            print(*compareList)




Measured memory_bytes: 5600
from sys import stdin

N, X = [int(x) for x in stdin.readline().rstrip().split()]
burger = [(1, 1)]
level = 0

while level < N:
    burger.append((burger[-1][0] * 2 + 3, burger[-1][1] * 2 + 1))
    level += 1

ans = 0
while N > 0 and X > 0:
    if X < burger[N - 1][0] + 2:
        N -= 1
        X -= 1
    if X == burger[N - 1][0] + 2:
        ans += 1
        X -= 2
        N -= 1
    if burger[N - 1][0] + 2 < X:
        X -= burger[N - 1][0] + 2
        ans += burger[N - 1][1] + 1
        N -= 1
if N == 0 and X > 0:
    ans += 1

print(ans)


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

int main() {
  int n;
  cin >> n;
  n = n%10;
  if(n==2 || n==4 || n==5 || n==7 || n==9){
    cout << "hon" << endl;
  } else if(n==0 || n==1 || n==6 || n==8) {
    cout << "pon" << endl;
  } else {
    cout << "bon" << endl;
  }
}


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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll N,ans,i,jud,j;
  vl H;
  cin >> N;
  vl B(N);
  REP(k,N){
		int x;
		cin >> x;
		H.push_back(x);
    B[k] = 0;
	}
  jud = 0;
  for(i=0;i<N-1;i++){
    if(H[i]>H[i+1]){
      j = i;
      while(B[j] == 0 && j>=0 && H[j]> H[j+1]){
        H[j] = H[j]-1;
        B[j] = 1;
        j = j-1;
      }
    }
  }
  for(i=0;i<N-1;i++){
    if(H[i]>H[i+1]){
      jud = 1;
    }
  }
  if(jud == 0){
    cout << "Yes"<< endl;
  }else{
    cout << "No"<< endl;
  }
  return 0;
}

Measured memory_bytes: 2168
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	public static void main(String args[]) {
		ConsoleScanner cin = new ConsoleScanner();
		PrintWriter cout = new PrintWriter(System.out);
		solve(cin, cout);
		cout.flush();
	}

	private static void solve(ConsoleScanner cin, PrintWriter cout) {
		// assert solve(1) == 1;

		int n = cin.nextInt();
		int m = cin.nextInt();
		int[][] abs = new int[m][];
		for (int i = 0; i < abs.length; i++)
			abs[i] = new int[] { cin.nextInt(), cin.nextInt() };

		long millis = System.currentTimeMillis();

		boolean ans = solve(n, m, abs);
		if (ans)
			cout.println("POSSIBLE");
		else
			cout.println("IMPOSSIBLE");

		assert null != cout.format("%d elapsed", System.currentTimeMillis() - millis);
	}

	private static boolean solve(int n, int m, int[][] abs) {
		Set<Long> ships = new HashSet<>();
		for (int[] ab : abs) {
			ships.add(((long) ab[0] << 30) + ab[1]);
			ships.add(((long) ab[1] << 30) + ab[0]);
		}
		for (int mid = 2; mid < n; mid++) {
			if (!ships.contains(((long) mid << 30) + 1))
				continue;
			if (!ships.contains(((long) mid << 30) + n))
				continue;
			return true;
		}
		return false;
	}

	static class ConsoleScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			try {
				while (!st.hasMoreElements())
					st = new StringTokenizer(br.readLine());
				return st.nextToken();
			} catch (IOException e) {
				throw new AssertionError(e);
			}
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}

}


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

void chmax(int& a, int b){
    a = max(a, b);
}

int main(){
    string S;
    cin >> S;
    int N = S.size();

    vector<vector<int>> dp(N+10, vector<int>(5, -1e9));
    dp[0][0] = 0;
    for(int i=0; i<N; i++) for(int j=0; j<=4; j++) for(int k=1; k<=4; k++){
        if(dp[i][j] >= 0 && S.substr(i-j, j) != S.substr(i, k)) chmax(dp[i+k][k], dp[i][j] + 1);
    }
    cout << *max_element(dp[N].begin(), dp[N].end()) << endl;
    return 0;
}


Measured memory_bytes: 13444
#include <stdio.h>

int main () {
    int N;
    int D;
    scanf("%d", &N);
    scanf("%d", &D);
    int k = 1;
    int ans = 0;
    for(;;) {
        if ((2 * k * D + k) >= N) {
            ans = k;
            break;
        }
        k++;
    }

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

    return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cstdlib>
#include<cmath>
#define range(i,a,b) for(int i = (a); i <= (b); i++)
#define rrange(i,a,b) for(int i = (a); i >= (b); i--)
#define rep(i,b) for(int i = 1; i <= (b); i++)
#define rrep(i,b) for(int i = (b); i >= 1; i--)
#define all(a) (a).begin(), (a).end()
#define show(x) cout << #x << " = " << (x) << endl;
using namespace std;
typedef long long ll;
const int N=1e5+11;
const int INF = 1001001001;
const ll LLINF = 1001001001001001001LL;
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
ll n,x,y,z; 
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
ll ll_read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
ll check(ll x,ll y){
	if((-x*n-y*n+4*x*y)>0&&((x*y*n)%(-x*n-y*n+4*x*y)==0)) return (x*y*n)/(-x*n-y*n+4*x*y);
	return 0;
}
int main(){
//	freopen("ex.in","r",stdin);
	n=ll_read();
	for(x=1;x<=3500;++x) for(y=1;y<=3500;++y) if(z=check(x,y)){
		printf("%lld %lld %lld",x,y,z);
		return 0;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>  
#include <cstdio>  
#include <cstdlib>  
#include <queue>  
using namespace std;  
  
const int N = 1000;  
const int INF = 0x3f3f3f3f;  
  
int n, m, f;  
char map[N][N+1];  
  
bool legal(int x, int y, int k)  
{  
    return x >= 0 && x < n && y >= 0 && y < m  
        && map[x][y] != 'X';  
}  
  
void input()  
{  
    cin >> n >> m >> f;  
    for (int i = 0; i < n; i ++) {  
        scanf("%s", map[i]);  
    }  
}  
  
int BFS(int k)  
{  
    int i, j;  
    int d[N][N];  
    typedef pair<int, int> P;  
    queue <P> q;  
    for (i = 0; i < n; i ++) {  
        for (j = 0; j < m; j ++) {  
            d[i][j] = INF;  
            if ((k == 0 && map[i][j] == 'S') || map[i][j] == '0'+k) {  
                q.push(P(i, j));  
                d[i][j] = 0;  
                map[i][j] = '.';  
            }  
        }  
    }  
  
    while( q.size() ) {  
        P p = q.front();  
        q.pop();  
        int x = p.first;  
        int y = p.second;  
  
        if (map[x][y] == INF)  
            return d[x][y];  
  
        int pos[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  
        for (i = 0; i < 4; i ++) {  
            int nx = x + pos[i][0];  
            int ny = y + pos[i][1];  
            if (legal(nx, ny, k) && d[nx][ny] == INF) {  
                q.push(P(nx, ny));  
                d[nx][ny] = d[x][y]+1;  
                if (map[nx][ny] == '0'+k+1) {  
                    return d[nx][ny];  
                }  
            }  
        }  
    }  
  
    return INF;  
}  
  
void solve()  
{  
    int res = 0;  
    for (int i = 0; i < f; i ++) {  
        res += BFS(i);  
    }  
    printf("%d\n", res);  
}  
  
int main(void)  
{  
    input();  
  
    solve();  
  
    return 0;  
}  


Measured memory_bytes: 8128
# -*- coding: utf-8 -*-

h, w = map(int, input().split())

if h == 1 or w == 1:
    print(1)
elif h % 2 == 0 and w % 2 == 0:
    print(int(h/2*w))
elif h % 2 == 0 and w % 2 != 0:
    print(int(h/2*w))
elif h % 2 != 0 and w % 2 == 0:
    print(int(h*w/2))
else:
    print(int((h*w+1)/2))

Measured memory_bytes: 3060
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int N;
ll a[100010][3];
ll dp[100010][3];

int main() {
	
	int N; cin >> N;
	rep(i, N) {
		for (int j = 0; j < 3; ++j) {
			cin >> a[i][j];
		}
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				if (j == k) continue;
				chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
			}
		}
	}
	ll res = 0;
	for(int j = 0; j < 3; ++j) chmax(res, dp[N][j]);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 4992
var main = function(input) {
  var X = parseInt(input);
  var max = 0;
  var I;
  for(var b=1;b<=X;b++){
    for(var p=2;p<10;p++){
    I = Math.pow(b,p);
      if(X<I){
        break;
      } 
      if(max<I){
      max = I;
      }
    }
  }
  console.log(max);
  return　 0;
}

main(require("fs").readFileSync("/dev/stdin", "utf8").trim());


Measured memory_bytes: 7372
INF = 2*10**9+1

H = int(input())
Heap = [-INF]
Heap += list(map(int,input().split()))

def maxHeapify(A,i):
    if i>= 1:
        l,r = i*2,i*2+1
        if l > len(A)-1:
            l,r = 0,0
        elif r > len(A)-1:
            r = 0
        if A[i] <= A[l] and A[r] <= A[l]:
            largest = l
        if A[l] <= A[r] and A[i] <= A[r]:
            largest = r
        if A[l] <= A[i] and A[r] <= A[i]:
            largest = i

        if largest != i and largest != 0:
            A[i],A[largest] = A[largest],A[i]
            maxHeapify(A,largest)

def buildMaxHeap(A):
    for i in reversed(range(1,H//2+1)):
        maxHeapify(A,i)

buildMaxHeap(Heap)
print(""," ".join(map(str,Heap[1:H+1])))



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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;

typedef set<int>::iterator sit;
typedef map<int, int>::iterator mit;
typedef vector<int>::iterator vit;

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;

#define _ % MOD
#define __ %= MOD

#define each(it, s) for (auto it = s.begin(); it != s.end(); ++it)
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.begin(), v.end(), greater<auto>())
#define fill(a) memset(a, 0, sizeof(a))

#define swap(a, b) \
	{              \
		a = a + b; \
		b = a - b; \
		a = a - b; \
	}
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repA(i, a, n) for (ll i = a; i <= (n); ++i)
#define repD(i, a, n) for (ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) << endl

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define fbo find_by_order
#define ook order_of_key

#define pv(a)                                 \
	{                                         \
		rep(i, a.size()) cout << a[i] << " "; \
		cout << endl;                         \
	}
#define mark(v) cout << "Here--" << v << endl;

const double EPS = (1e-7);
int dcmp(double x, double y) { return fabs(x - y) <= EPS ? 0 : x < y ? -1 : 1; }

ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}
ll power(ll x, ll y)
{
	ll res = 1;
	while (y > 0)
	{
		if (y & 1)
			res = res * x;
		y = y >> 1;
		x = x * x;
	}
	return res;
} // modular exponent

vector<vector<ll>> matmul(vector<vector<ll>> A, vector<vector<ll>> B)
{
	vector<vector<ll>> ans(A.size(), vector<ll>(B[0].size(), 0));
	rep(i, A.size())
	{
		rep(j, B[0].size())
		{
			rep(k, A.size())
			{
				ans[i][j] = (ans[i][j] + A[i][k] * B[k][j]) % MOD;
			}
		}
	}
	return ans;
}

vector<vector<ll>> matpow(vector<vector<ll>> A, ll exp)
{
	if (exp == 1)
		return A;
	vector<vector<ll>> res = matpow(A, exp / 2);
	if (exp % 2 == 0)
		return matmul(res, res);
	return matmul(matmul(A, res), res);
}

ll solve(vector<vector<ll>> adj, ll n, ll k)
{
	vector<vector<ll>> ak = matpow(adj, k);
	ll ans = 0;
	rep(i, adj.size())
	{
		rep(j, adj.size())
		{
			ans = (ans + ak[i][j]) % MOD;
		}
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false); // don't use printf and scanf
	cin.tie(NULL);					  // cout<<fixed<<setprecision

	ll n, k;
	cin >> n >> k;
	vector<vector<ll>> adj(n, vector<ll>(n, 0));
	rep(i, n)
	{
		rep(j, n)
		{
			cin >> adj[i][j];
		}
	}
	ll ans = solve(adj, n, k);
	cout << ans << endl;
	return 0;
}

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

#define endl '\n'

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, p;
    string s;
    cin >> n >> p >> s;
    long long ans = 0;
    if (p == 2 || p == 5){
        for (int i=0; i<n; i++) if ( (s[i] - '0') % p == 0) ans += i+1;
    } else{
        map<int, int> freq;
        freq[0] = 1;
        int ac = 0, pot = 1;
        for (int i=n-1; i>=0; i--){
            ac = ((s[i] - '0')*pot + ac)%p;
            ans += freq[ac]++;
            pot = (pot*10)%p;
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 916
N = int(input())
A = list(map(int, input().split()))
ans = [0] * 9

for i in range(N):
  aa = int(A[i] / 400)
  if aa > 8:
    aa = 8
  ans[aa] += 1
  
min_a = 0
max_a = 0
for i in range(9):
  if i != 8:
    if ans[i] != 0:
      min_a += 1
      max_a += 1
  else:
    max_a += ans[i]
    
min_a = max(min_a, 1)    
print(min_a, max_a)





Measured memory_bytes: 9196
n = int(input())
A=[int(i) for i in input().split()]
MOD = 1000000007
ans = 1
cnt = [0]*(n+1)
cnt[0]=3

for i in range(n):
    ans = ans * cnt[A[i]] %MOD
    cnt[A[i]]-=1
    cnt[A[i]+1]+=1
    if ans==0:
        break
print(ans)


Measured memory_bytes: 13964
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt(), N = sc.nextInt();
    int sum = 0;
    for (int i = 0; i < N; i++) sum += sc.nextInt();
    System.out.println((sum >= H) ? "Yes" : "No");
  }
}

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int main(int argc, const char * argv[]) {
    // source code
    int n, k , q;
    cin >> n >> k >> q;
    vector<int> a(n, 0);
    rep (i, q) {
        int in;
        cin >> in;
        a[--in]++;
    }
    
    rep (i, n) {
        if (a[i] <= q - k)  cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}


Measured memory_bytes: 1024
chomp($s=<>);
($sx,$sy,$tx,$ty) = split/ /,$s;

$ucnt=$ty-$sy;
$rcnt=$tx-$sx;

$val= 'U' x $ucnt;
$val.= 'R' x $rcnt;
$val.= 'D' x $ucnt;
$val.= 'L' x $rcnt;
$val.= 'L';
$val.= 'U' x ($ucnt+1);
$val.= 'R' x ($rcnt+1);
$val.= 'D';
$val.= 'R';
$val.= 'D' x ($ucnt+1);
$val.= 'L' x ($rcnt+1);
$val.= 'U';
print $val;

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

#define F first
#define S second
#define pb push_back
#define mp make_pair

ll gcd(ll a, ll b){
	if (a == 0) return b;
	return gcd(b%a, a);
}

ll lcm(ll a, ll b){
	return (a/gcd(a, b))*b;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll n,x,y,i,j;

	double d;

	cin >> n >> d;

	ll cnt = 0;
	for(i=0;i<n;i++)
	{
		cin >> x >> y;

		if((double)(sqrt(pow(x,2) + pow(y,2))) <= d)
			cnt++;
	}

	cout << cnt << endl;
}

Measured memory_bytes: 3760
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;  
int main(){
	int n;
	long long a[10000];	
	scanf("%d",&n);
	a[0]=2;if(n==0) printf("2");
	a[1]=1;if(n==1) printf("1");
	else { for(int i=2;i<=n;i++){
	a[i]=a[i-1]+a[i-2];
	}
	printf("%lld\n",a[n]);
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
#define ii for(int i=1;i<=n;++i)
#define ji for(int j=1;j<=n;++j)
#define jj for(int j=1;j<=m;++j)
#define ij for(int i=1;i<=m;++i)
#define sz(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
#define alll(x) x+1,x+1+n
#define asd cout<<"ok"<<endl;
#define endl '\n'

int a[100005];
int main()
{
    string s;
    cin>>s;
    int n=s.size();
    ii a[i]=(s[i-1]=='1');
    if(a[n]) return cout<<-1<<endl,0;
    if(!a[1] || !a[n-1]) return cout<<-1<<endl,0;
    for(int i=2;i<=n-2;++i) if(a[i] && !a[n-i]) return cout<<-1<<endl,0;
    int tp = 0, rt = 0, sz = 0;
    vector<pair<int,int>> ans;
    for(int i=2;i<=n/2;++i)
    {
        if(a[i])
        {
            ++tp;
            int nxt = tp;
            if(sz) ans.push_back({nxt, rt});
            for(int j=1;j<=i-sz-1;++j) ans.push_back({nxt,++tp});
            rt = nxt;
            sz = i;
        }
    }
    int nxt = ++tp;
    if(sz) ans.push_back({nxt, rt});
    for(int j=1;j<=n-sz-1;++j) ans.push_back({nxt,++tp});
    for(auto p:ans) cout<<p.first<<" "<<p.second<<endl;
}

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

int main()
{
    int N;
    cin>>N;
    int K=N%10;
    N=N/10;
    if(K==9)
        cout<<"Yes"<<endl;
    else
    {
        if(N==9)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

vector<ll> num;

vector<map<ll, pair<bool, ll>>> memo;

ll f(ll l, ll n) {
    if (n <= 0) {
        return 0;
    }
    if (l == 0) {
        return 1;
    }

    auto& curr = memo[l][n];
    if (curr.first) {
        return curr.second;
    }
    curr.first = true;

    ll result = 0;

    //B
    n--;

    //L-1バーガー
    result += f(l - 1, min(n, num[l - 1]));
    n -= num[l - 1];

    //P
    if (n-- >= 1) {
        result++;
    }

    //L-1バーガー
    result += f(l - 1, min(n, num[l - 1]));
    n -= num[l - 1];

    //B
    n--;

    return curr.second = result;
}

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

    num.resize(N, 1);
    for (ll i = 1; i < N; i++) {
        num[i] = 2 * num[i - 1] + 3;
    }

    memo.resize(N + 1);

    cout << f(N, X) << endl;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class CTreeRestoring {
public:
    static constexpr int kStressIterations = 0;
    static void generateTest(std::ostream& test) {
    }

    void solve(std::istream& cin, std::ostream& cout) {
        int N;
        cin >> N;

        vector<int> a(N);
        REP(i, N) cin >> a[i];

        vector<int> d(101, 0);
        int len = 0;
        REP(i, N) {
            d[a[i]]++;
            len = max(a[i], len);
        }

        int pivot = len / 2;
        if (len & 1) pivot++;

        REP(i, pivot) {
            if (d[i] > 0) {
                cout << "Impossible" << endl;
                return;
            }
        }

        if (len % 2 == 0) {
            if (d[pivot] != 1) {
                cout << "Impossible" << endl;
                return;
            }
        } else {
            if (d[pivot] != 2) {
                cout << "Impossible" << endl;
                return;
            }
        }

        FOR(i, pivot + 1, len) {
            if (d[i] < 2) {
                cout << "Impossible" << endl;
                return;
            }
        }

        cout << "Possible" << endl;
        return;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    CTreeRestoring solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _090
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int A = Convert.ToInt32(str[0]);
            int B = Convert.ToInt32(str[1]);

            
            int count = 0;

            for(int i = A; i <= B; ++i)
            {
                string m = Convert.ToString(i);
                char[] a = m.ToCharArray();
                Array.Reverse(a);
                string n =  new string(a);

                int x = Convert.ToInt32(n);
                int y = i;
                if (x == y)
                {
                    count = count + 1;
                }

                

            }

            Console.WriteLine(count);
            Console.Read();

        }
    }
}

Measured memory_bytes: 17356
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;


ll gcd(ll x,ll y){
  return y==0? x:gcd(y,x%y);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,K;cin>>N>>K;
  vint l(N);
  repeat(i,N)cin>>l[i];
  sort(l.begin(),l.end(),greater<int>());
  int ans = 0;
  repeat(i,K){
    ans += l[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define vi vector<int>
#define LLMAX 4000000000000000000LL
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
struct edge
{
	int t, f, w;
	bool operator < (const edge& e) const
	{
		return w > e.w;
	}
	edge(int from, int to, int weight)
	{
		t = to;
		f = from;
		w = weight;
	}
};
#define ii pair<int,int>
#define MOD 1000000007
const double EPS = (1e-5);
long long binpow(long long a, long long b){long long res = 1;while (b > 0){if (b & 1)res = res * a;a = a * a;b >>= 1;}return res;}
int findXOR(int n){switch (n % 4){case 0:return n;case 1:return 1;case 2:return n + 1;case 3:return 0;}}
int rangeXOR(int l, int r){return (findXOR(l - 1) ^ findXOR(r));}
int getbit(int mask, int bit){return (mask & (1 << bit));}void setbit(int& mask, int bit, int val){if (val)mask |= (1 << bit);else mask &= ~(1 << bit);}
//ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
//ll lcm(ll a, ll b){return a * (b / gcd(a, b));}
const int N = 1e5+10;
const int M = 101;
const ll INF = 1e9;
int w[M],v[M];
ll dp[2][N];
void solve()
{
	int n, W;
	cin >> n >> W;
	for (int i = 0; i < n; ++i)
		cin >> w[i] >> v[i];
	int x = 0;
	dp[x][w[0]] = v[0];
	for (int i = 1; i < n; ++i)
	{
		x ^= 1;
		for (int j = 0; j <= W; ++j)
		{
			if (j + w[i] <= W)
			{
				dp[x][j + w[i]] = max(dp[x][j + w[i]], v[i] + dp[x ^ 1][j]);
			}
			dp[x][j] = max(dp[x][j],dp[x ^ 1][j]);
		}
	}
	ll ans = 0;
	for (int i = 0; i <= W; ++i)
		ans = max(ans, dp[x][i]);
	cout << ans << '\n';

}
int main(void)
{
	//freopen("commandos.in", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tc = 1;
	//cin >> tc;
	//scanf("%d", &tc);
	while (tc--)
	{
		solve();
	}
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
 
#define LOCAL  1
#define UPLOAD 2
 
#define ll long long
const long long INF = 1LL << 60;
 
template <class T = long long> T input(){T x;cin >> x;return x;}
template <class T> void output(T x){cout << x << endl;}
#define debug(x) cerr << #x<< ": " << x<< '\n';
#define debugBit(x,n) cerr << #x<< ": " << std::bitset<n>(x) << '\n';
#define REP(i,M) for(int i=0;i<M;i++)
 
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
 
int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

  ll l = input();
  float ret = pow(l/3.0, 3);
  cout << fixed << setprecision(15) << ret << endl;

  return 0;
}

Measured memory_bytes: 384
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double pi = acos(-1);
const ll SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[200005], finv[200005], inv[200005];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) {
	for (auto &e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

//↑template↑





int main() {

	long double a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << setprecision(20) << (long double)(a*b / 2.0) << endl;

	if (a / 2.0 == c && b / 2.0 == d) { cout << 1 << endl; }
	else { cout << 0 << endl; }


}

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;
#define pow10(n) int(1e##n + n)

void solve()
{
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<int> d(N);

    REP1 (i, N - 1)
    {
        FOR (j, i + 1, N + 1)
        {
            d[min(min(abs(i - j), abs(X - i) + 1 + abs(Y - j)), abs(X - j) + 1 + abs(Y - i))]++;
        }
    }
    REP1 (i, N - 1)
    {
        cout << d[i] << endl;
    }
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define se second
#define fr first
using namespace std;

const ll N = 2e5 + 7;
ll n , m , k , a , cnt , ans;
vector<pair< ll , ll > >p;
map<ll , ll>mp;
int main()
{
    cin >> n;
    if( n == 1 )
        cout << 0;
    else
        cout << 1;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<long long> v(n), b(n, 0);
    long long all = 0, t = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i]; all += v[i];
        if (i % 2 == 0) t += v[i]; 
    }
    all /= 2; t -= all;
    b[0] = t;
    for (int i = 1; i < n; i++) {
        b[i] = v[i-1] - b[i-1];
    }
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << b[i] * 2;
    }
    return 0;
}

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

int main(){
    string s;
    cin >> s;
    
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(),s.end()), s.end());
    char ch = 'a';
    
    //cout << s << endl;
    bool flag = false;
    int cnt=0;
    for(int i=0; i<s.length(); i++){
        if(s[i] != ch){
            cout << ch << endl;
            flag=true;
            break;
        }
        cnt++;
        ch++;
    }
    //cout << cnt << endl;
    if(!flag){
        if(cnt==26)
            cout << "None" << endl;
        else
            cout << ch << endl;
    }
}


Measured memory_bytes: 512
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = []

# 全て正
if min(A)>=0:
    print(sum(A)-2*A[0])
    for i in range(n):
        if i==0:
            x = A[i]
        elif i==n-1:
            print(A[i], x)
        else:
            print(x, A[i])
            x -= A[i]

# 全て負
elif max(A)<=0:
    A = A[::-1]
    print(sum(A)*(-1)+2*A[0])
    for i in range(n):
        if i==0:
            x = A[i]
        else:
            print(x, A[i])
            x -= A[i]

# 正負
else:
    m,p = [], []
    for a in A:
        if a<0:
            m.append(a)
        else:
            p.append(a)
    print(sum(p)-sum(m))
    m.sort()
    p.sort()
    x = m[0]
    for i in range(len(p)-1):
        print(x, p[i])
        x -= p[i]
    else:
        print(p[-1], x)
        x = p[-1] - x
        
    for j in range(1, len(m)):
        print(x, m[j])
        x -= m[j]

Measured memory_bytes: 14260
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int cnt = 0;
		int tot = 0;
		for(int i=0;i<N;i++){
			if(i == 0 || A[i-1] != A[i]){
				int a = tot / 2;
				cnt += a;
				tot = 1;
			} else {
				tot++;
			}
		}
		if(tot > 0){
			int a = (tot) / 2;
			cnt += a;
		}
		Console.WriteLine(cnt);
	}
	int N;
	int[] A;
	public Sol(){
		N = ri();
		A = ria();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define mp            make_pair
#define pb            push_back
template<class T1, class T2> inline void minup(T1& m, T2 x){ if(m>x) m=static_cast<T2>(x); }
template<class T1, class T2> inline void maxup(T1& m, T2 x){ if(m<x) m=static_cast<T2>(x); }

#define INF 1000000000
#define MOD 1000000007
#define EPS 1E-12

string s[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int y, m, d;

int main()
{
  while((cin >> m >> d) && m){
    y = 2004;
    if(m == 1) y = 2003, m = 13;
    if(m == 2) y = 2003, m = 14;
    int D = (d + 26*(m+1)/10 + y + y/4 +5*(y/100) + y/100/4 + 4) % 7;
    cout << s[D] << endl;
  }


  return 0;
}

Measured memory_bytes: 1192
#B
nr = list(input())
diff = int(100000)
ndiff = int(0)

for a in range(len(nr) - 2):
    ndiff = abs(((int(nr[a])*100 + int(nr[a+1])*10 + int(nr[a+2])) - 753))
    if ndiff < diff:
        diff = ndiff
print(diff)

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

int main(){
  vector<int> A(3);
  cin>>A.at(0)>>A.at(1)>>A.at(2);
  
  sort(A.begin(),A.end());
  cout<<A.at(0)+A.at(1)+10*A.at(2)<<endl;
}

Measured memory_bytes: 256
import java.math.BigDecimal

fun solver(n: Int, aList: List<Int>): BigDecimal {
    var sum = BigDecimal.ZERO
    var base = 0

    aList.forEach { a ->
        base = maxOf(base, a)
        if (base > a) {
            sum = sum.add(BigDecimal(base - a))
        }
    }


    return sum
}

fun main(args: Array<String>) {
    val n =  readLine()!!.toInt()
    val aList = readLine()!!.split(" ").map { it.toInt() }     

    //val n = 5
    //val aList = listOf(3, 200000, 3, 3, 3)

    val result = solver(n, aList)

    println(result.toString())
}


Measured memory_bytes: 69448
n, q = map(int, input().split())
BIT = [0] * (n + 1)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s
a = list(map(int, input().split()))
for i in range(n):
    add(i + 1, a[i])
for i in range(q):
    x, y, z = map(int, input().split())
    if x == 0:
        add(y + 1, z)
    else:
        print(query(z) - query(y))

Measured memory_bytes: 68784
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <list> 
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<string>
#include<fstream>
#include<set>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define forl(i,a,n) for(int i=a;i<n;i++)
#define rfor(i,n,a) for(int i=n;i>=a;i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define ld long double
#define vi vector<int>
#define vll vector<long long>
#define pi pair<int,int>
#define pll pair<long long,long long>
#define mp make_pair
#define B begin()
#define E end()
#define S size()
#define m9 1000000007
#define endl "\n"
using namespace std;
 
 

 
ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

ll powmod(ll x, ll y, ll m) 
{ 
    if (y == 0) 
        return 1; 
    ll p = powmod(x, y/2, m) % m; 
    p = (p * p) % m; 
    return (y%2 == 0)? p : (x * p) % m; 
} 

 
ll mul_inv(ll a, ll b) {
    ll b0 = b, t, q;
    ll x0 = 0ll, x1 = 1ll;
    if (b == 1ll) return 1ll;
    while (a > 1ll) {
        q = a / b;
        t = b, b = a % b, a = t;
        t = x0, x0 = x1 - q * x0, x1 = t;
    }
    if (x1 < 0ll) x1 += b0;
    return x1;
}
 
 
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
#define pin(a) for(auto x:a)cout<<x<<" ";cout<<endl
#define fck(a) cout<<a;exit(0)
#define vvll vector<vector<ll> >
#define A(b) b.begin(),b.end()
#define vpi std::vector<pll>
#include <array>
#include <stack>
#define arr2 array<ll,2>
#define arr3 array<ll,3>
#define varr2 vector<array<ll,2> >
#define varr3 vector<array<ll,3> >
//include<bits/stdc++.h>
 
 
bool fa(vll &x,vll &y){return x[0]<y[0];}
bool fa1(vll &x,vll &y){return x[1]<y[1];}
bool f1(pll &x,pll &y){return x.second>y.second;}
bool f2(pll &x,pll &y){
    return x.first>y.first;
}
 
 
bool f3(ll &x,ll &y){
    return x>y; 
    }


const ll maxn=2e5+2;





int main()
{ fastio;
//freopen("input.txt, "r", stdin); 
//freopen("output.txt", "w", stdout);

ll n,q;cin>>n>>q;
ll b[n];
forl(i,0,n)cin>>b[i];
vll seg(n+n,0ll);
vector<varr2>gr(n+1);
ll ans[q];
forl(i,0,q){
ll x,y;cin>>x>>y;
x--;y--;
gr[y].pb({x,i});
}
vll h(n+1,-1ll);
forl(i,0,n){
    ll p1=i;
    for(seg[p1+=n]=1;p1>1;p1>>=1){
        seg[p1>>1]=seg[p1]+seg[p1^1];
    }
    if(h[b[i]]!=-1){
        p1=h[b[i]];
    for(seg[p1+=n]=0;p1>1;p1>>=1){
        seg[p1>>1]=seg[p1]+seg[p1^1];
    }
    }
    h[b[i]]=i;
    for(auto f:gr[i]){
        ll l=f[0],r=i+1;
        ll x=0;
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l%2){
                x+=seg[l++];
            }
            if(r%2){
                x+=seg[--r];
            }
        }
        ans[f[1]]=x;
    }
}

forl(i,0,q){
    cout<<ans[i]<<"\n";
}
  







return 0;
}





  







Measured memory_bytes: 48172
#include <iostream>
using namespace std;
void ABC100(void);
void ABC101(void);
void ABC102(void);
void ABC103(void);
void ABC104(void);
void ABC105(void);
void ABC106(void);
void ABC107(void);
void ABC108(void);
void ABC109(void);

int main(void){
    ABC109();
}

void ABC109(){
    int a,b;
    cin>>a>>b;
    if(a%2==0||b%2==0)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
import fractions
a,b=map(int,input().split())
n=fractions.gcd(a,b)

if n==1:
  print(1)
  exit()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

print(len(factorization(n))+1)


Measured memory_bytes: 5048
#include <stdio.h>
int main(void)
{
    int w,n;
    int i,j,temp=0;
    int a[30],b[30];
    int c[30],out[30];

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

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

    for(i=1;i<=w;i++){
        c[i]=i;
        for(j=1;j<=n;j++){
            if(c[i]==a[j]){
                c[i]=b[j];
            }else if(c[i]==b[j]){
                c[i]=a[j];
            }
        }
 //       printf("%d\n",c[i]);
        temp=c[i];
        out[temp]=i;
        
//        iがn番目
  //      out[c[i]]=i;
 //       printf("%d\n",temp);
    }
    for(i=1;i<=w;i++){
        printf("%d\n",out[i]);
    }
    
    return 0;
}


Measured memory_bytes: 2040
/*    Author: arpitp699
    ----ARPIT PATEL----
*/
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vi vector<int> 
#define vvi vector<vi>
#define vvl vector<vl>
#define vl vector<ll>
#define vpi vector<pi> 
#define vpl vector<pl>

#define PB emplace_back
#define MP make_pair
#define SZ(x) (ll)x.size()
#define SS second
#define FF first

#ifdef LOCAL
#define error(args...) { griding _s = #args; replace(_s.begin(), _s.end(), ',', ' '); gridinggrideam _ss(_s); igrideam_iterator<griding> _it(_ss); err(_it, args); }
#define debugVec(a) cout<<"#### = "<<#a<<endl; for(auto x:a) cout<<x<<" "; cout<<endl;
#define debug(a) cout<<"#### = "<<#a<<endl; for(auto x:a){ cout<<x.FF<<" "<<x.SS<<endl;}
#endif

#ifdef ONLINE_JUDGE
#define error(args...)
#define debugVec(a) 
#define debug(a)
#endif

#define endl "\n"
#define MOD 1000000007
#define MAX 100010

#define ALL(x) x.begin(),x.end()
#define REP(i,a,n) for(ll i=a;i<n;++i)
#define REPR(i,n,b) for(ll i=n;i>=b;i--)
#define tr(x, it) for(typeof(x.begin()) it = x.begin(); it != x.end(); it++)

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int test=1;
    // cin>>test;
    while(test--){
        int h,w; cin>>h>>w;

        vector<string> grid(h);
        REP(i,0,h){
            string str; cin>>str;
            grid[i]=str;
        } 

        vvi dp(h,vi(w,INT_MAX));
        if(grid[0][0]!='.') dp[0][0]=1;
        else
            dp[0][0]=0;

        REP(i,1,h){
            if(grid[i][0]=='#'){
                if(grid[i-1][0]=='#') dp[i][0]=dp[i-1][0];
                else dp[i][0]=1+dp[i-1][0];
            }
            else dp[i][0]=dp[i-1][0];
        }

        REP(i,1,w){
            if(grid[0][i]=='#'){
               if(grid[0][i-1]=='#') dp[0][i]=dp[0][i-1];
               else dp[0][i]=dp[0][i-1]+1;
            }
            else{
                dp[0][i]=dp[0][i-1];
            }
        }

        REP(i,1,h){
            REP(j,1,w){
                if(grid[i][j]=='.'){
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1]);
                }
                else{
                    if(grid[i-1][j]=='#'){
                        dp[i][j]=dp[i-1][j];
                    }
                    else if(grid[i-1][j]=='.'){
                        dp[i][j]=dp[i-1][j]+1;
                    }
                    if(grid[i][j-1]=='.'){
                        dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
                    }
                    else if(grid[i][j-1]=='#'){
                        dp[i][j]=min(dp[i][j],dp[i][j-1]);
                    }
                }
            }
        }

       /* REP(i,0,h){
            cout<<i<<"->>";
            REP(j,0,w){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }*/

        cout<<dp[h-1][w-1]<<endl;
    }
}

Measured memory_bytes: 384
#include<iostream>
#include<map>
using namespace std;

int main(void){
	int n,m;
	while(cin >> n, n != 0){
		char c, d;
		map<char, char> tb;
		for(int i = 0; i < n; i++){
			cin >> c >> d;
			tb[c] = d;
		}
		cin >> m;
		for(int i = 0; i < m; i++){
			cin >> c;
			if(tb.find(c) != tb.end())
				cout << tb[c];
			else
				cout << c;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1188