akhauriyash/Code-Regression huggingface dataset:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n, m, q = MAP()
'''
arr = [[]]
for i in range(n):
    tmp = deepcopy(arr)
    arr = []
    for j in range(1, m + 1):
        for k in range(len(tmp)):
            if len(tmp[k]) == 0 or tmp[k][-1] <= j:
                arr.append(deepcopy(tmp[k]))
                arr[-1].append(j)
'''
arr = list(combinations_with_replacement(range(1, m + 1), n))
point = [0 for _ in range(len(arr))]
for i in range(q):
    a, b, c, d = MAP()
    for j in range(len(arr)):
        if arr[j][b - 1] - arr[j][a - 1] == c:
            point[j] += d

print(max(point))


Measured memory_bytes: 85908
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace I
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var N = int.Parse(Console.ReadLine());
            var P = Console.ReadLine().Trim().Split(' ').Select(double.Parse).ToArray();
            var dp = new double[N + 1][].Select(x => x = new double[N + 1]).ToArray();
            dp[0][0] = 1;
            for (var i = 0; i < N; i++)
            {
                var p = P[i];
                var q = 1 - p;
                for (var j = 0; j <= i; j++)
                {
                    dp[i + 1][j + 1] += dp[i][j] * p;
                    dp[i + 1][j] += dp[i][j] * q;
                }
            }
            var answer = 0d;
            for (var i = N / 2 + 1; i <= N; i++)
            {
                answer += dp[N][i];
            }

            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 99888
#include <stdio.h>

int main(void) {
	// your code goes here

	 char a;
  scanf("%c", &a);
 
  if((a >= 'a') && (a <= 'z')) printf("%c\n", 'a');
  if((a >= 'A') && (a <= 'Z')) printf("%c\n", 'A');
 
	return 0;
}


Measured memory_bytes: 1648
#include<cstdio>
int n;
char A[2010],B[2010];
int last[2010],next[2010],val[2010];
void cmin(int&a,int b){b<a?a=b:1;}
void cmax(int&a,int b){b>a?a=b:1;}
int main(){
	scanf("%s%s",A,B);
	for(;A[n];n++)A[n]-='0',B[n]-='0';
	int ans=1<<30;
	for(int o=0;o<n;o++)if(B[o]){
		last[o]=next[o]=0;
		for(int i=(o+1)%n;i!=o;i=(i+1)%n)last[i]=B[i]?0:last[(i+n-1)%n]+1;
		for(int i=(o+n-1)%n;i!=o;i=(i+n-1)%n)next[i]=B[i]?0:next[(i+1)%n]+1;
		for(int d=0;d<n;d++){
			int cnt=0;
			for(int i=0;i<n;i++)val[i]=i>d?0:n;
			for(int i=0;i<n;i++)if(A[i]!=B[(i+d)%n]){
				cnt++;
				if(next[i]>d)cmax(val[n-last[i]],next[i]);
				if(last[i]>n-d)cmin(val[next[i]],n-last[i]);
			}
			int r=d;
			for(int i=d+1;i<=n;i++){
				cmin(ans,cnt+d+2*(r-d)+2*(n-i));
				cmax(r,val[i]);
			}
			r=d;
			for(int i=d;i>=0;i--){
				cmin(ans,cnt+n-d+2*i+2*(d-r));
				cmin(r,val[i]);
			}
		}
		printf("%d\n",ans);
		return 0;
	}
	for(int o=0;o<n;o++)if(A[o])return puts("-1"),0;
	return puts("0"),0;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  int N;
  cin >> N;
  vector<long long> xpy(N), xmy(N), ypx(N), ymx(N);
  for(int i = 0; i < N; i++){  
    int x, y;
    cin >> x >> y;
    xpy[i] = x + y;
    xmy[i] = x - y;
    ypx[i] = -1 * (x + y);
    ymx[i] = y - x;
  }
  sort(xpy.begin(), xpy.end());
  sort(ypx.begin(), ypx.end());
  sort(xmy.begin(), xmy.end());
  sort(ymx.begin(), ymx.end());
  cout << max({xpy[N-1] - xpy[0], ymx[N-1] - ymx[0], ypx[N-1] - ypx[0], xmy[N-1] - xmy[0]}) <<endl;
} 


Measured memory_bytes: 9528
#include<iostream>
#include<string>
using namespace std;

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;

    if(N%2!=0){
        cout << "No" << endl;
    }else{
        string T,U;
        T=S.substr(0,N/2);
        U=S.substr(N/2, N/2);

        //cout << T << " " << U << endl;

        if(T==U){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        r: i64,
    }

    let ans = r * r;

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
#define sqr(x) ((x)*(x))
#define mp make_pair
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define getchar gc
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
int n,flag;
string s;
int main(){
	cin>>s;
	n=s.length();
	for(int i=0;i<n;i++)if(s[i]!='0')flag=1;
	if(!flag){
		cout<<n<<endl; return 0;
	}
	if(n%2==0){
	    for(int i=n/2;i<n;i++){
		if(s[i]!=s[n-i-1]||s[i]!=s[i-1]){
			cout<<i<<endl; return 0;
		}
	}cout<<n<<endl;}else{
		for(int i=n/2+1;i<n;i++)if(s[i]!=s[n-i-1]||s[i]!=s[i-1]){
			cout<<i<<endl; return 0;
		}
		cout<<n<<endl;
	}
}

Measured memory_bytes: 1144
using namespace std;
#include<bits/stdc++.h>
#define int long long
#define pb push_back 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define repa(i,a,b) for (int i=a; i<=b; i++)
#define repd(i,b,a) for (int i=b; i>=a; i--)
#define endl "\n"
//debugging
#define debug1(a) cout<<#a<<" = "<<(a)<<endl;
#define debug2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define debug3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;
#define debug4(a,b,c,d) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<", "<<#d<<" = "<<(d)<<endl;

const int N = 1e+6+5;
int BIG = 1e+18+3;
int mod = 1e+9+7;

signed main()
{
    IOS;
    
    int n,k; cin>>n>>k;

    int h[n+1];
    int cost[n+1];

    repa(i,1,n) cin>>h[i];

    int dp[n+1];

    repa(i,1,n) dp[i] = BIG;

    dp[1] = 0;
    dp[2] = abs(h[2]-h[1]);

    repa(i,3,n)
        repd( j, i-1, max( i-k, (int)1) )
            dp[i] = min(dp[i], abs(h[i]-h[j]) + dp[j] );
    
    cout<< dp[n] <<endl;
}

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


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

	string S, T; cin >> S >> T;
	int sum = 0;
	for (int i = 0; i < 3; i++) {
		if (S[i] == T[i])sum++;
	}
	cout << sum;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	// "math"
)

func main() {
	var n int
	fmt.Scan(&n)

	var d [50]int
	for i := 0; i < n; i++ {
		var x int
		fmt.Scan(&x)
		d[i] = x
	}

	sum := 0
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			// fmt.Println(d[i], d[j], d[i]*d[j])
			sum += d[i] * d[j]
		}
	}
	fmt.Println(sum)
}


Measured memory_bytes: 512
def f(n):
  if n % 2 == 0:
    return n / 2
  else:
    return 3 * n + 1

s = int(input())
n = 2
l = []
l.append(s)
while True:
  s = f(s)
  if s in l:
    break
  else:
    l.append(s)
    n += 1
    
print(n)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long int ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
const int MOD=1000000007;
#define pp pair<ll,ll>
bool isPowerOfTwo (ll x)  
{  
    return x && (!(x&(x-1)));  
}
bool isPrime(int n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
}
int highestPowerof2(unsigned int n) 
{ 
    // Invalid input 
    if (n < 1) 
        return 0; 
  
    int res = 1;
    for (int i=0; i<8*sizeof(unsigned int); i++) 
    { 
        int curr = 1 << i; 
        if (curr > n) 
           break; 
  
        res = curr; 
    } 
  
    return res; 
} 
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;
}
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
/*lcm(gcd(N1, M), gcd(N2, M), ..., gcd(Nk, M)) = gcd(lcm(N1, ..., Nk), M)
gcd(lcm(N1, M), lcm(N2, M), ..., lcm(Nk, M)) = lcm(gcd(N1, ..., Nk), M).

If gcd(N1, N2) = 1, then
gcd(N1·N2, M) = gcd(N1, M)·gcd(N2, M)
lcm(N1·N2, M) = lcm(N1, M)·lcm(N2, M)/M.

lcm(M, N, P) · gcd(M, N) · gcd(N, P) · gcd(P, M) = NMP · gcd(N, M, P).
*/
////////////////////////////////////////////////////////////////////

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);  
  cout.tie(NULL);
  int t=1;
  while(t--)
  {
    ll n,k;
    cin>>n>>k;
    ll gc=0,a,m=0;
    REP(i,n)
    {
        cin>>a;
        m=max(m,a);
        gc=__gcd(a,gc);
    }
    if(k%gc == 0 && k<=m)cout<<"POSSIBLE";
    else cout<<"IMPOSSIBLE";
  }  
  return 0;
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* 1LL<<i and not 1<<i
* overflow (int vs ll?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

Measured memory_bytes: 256
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A =  [list(map(int, input().split())) for i in range(N)]

count = 0

for i in range(N):
    tmp = C
    for j in range(M):
        tmp += A[i][j] * B[j]
    if(tmp > 0): count += 1

print(count)

Measured memory_bytes: 3316
from sys import stdin


def get_result(data):
    N, K = data
    q, mod = divmod(N, K)
    ans = min([mod, abs(mod-K)])
    return ans


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define sort(a) sort(all(a))
using P = pair<int, int>;
using ll = long long;
using ld = long double;
typedef vector<int> vi;
int dx[4] = { 0, 1, 0,-1 };
int dy[4] = { 1, 0,-1, 0 };
const ll MOD = 1000000007;

signed main() {
  string S,T;
  cin >> S >> T;
  int ans =0;
  for (int i = 0; i < S.size(); i++) {
    if(S[i]!=T[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3860
#include <stdio.h>

int selectionSort(int *a, int n);
void swap(int *a, int *b);

int main(int argc, char const *argv[])
{
  int a[100],n,i,count;
  scanf("%d", &n);
  for(i=0;i<n;i++) {
    scanf("%d", a+i);
  }
  count = selectionSort(a,n);
  for(i=0;i<n-1;i++)
    printf("%d ", a[i]);
  printf("%d\n", a[n-1]);
  printf("%d\n", count);
  return 0;
}

int selectionSort(int *a, int n)
{
  int i,j,count=0, minj;
  for(i=0;i<n;i++) {
    minj = i;
    for(j=i;j<n;j++) {
      if(a[j]<a[minj])
        minj = j;
    }
    if(minj != i) {
      swap(a+i,a+minj);
      count += 1;
    }
  }
  return count;
}

void swap(int *a, int *b)
{
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

Measured memory_bytes: 2752
import Control.Applicative
import Control.Monad
import Data.List
import Data.Char
import Data.Maybe
strToInt s = (read :: String -> Int) s
strToInteger s = (read :: String -> Integer) s
strToDouble s = (read :: String -> Double) s

main :: IO ()
main = do
	n <- readLn
	xs <- sort . map strToInt . words <$> getLine
	putStrLn . show $ xs!!(n-1) - xs!!0


Measured memory_bytes: 1020
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

template<class Monoid> struct SegmentTree {
private:
    using Func = std::function<Monoid(Monoid, Monoid)>;
    Func F;
    Monoid UNITY;
    int n;
    std::vector<Monoid> node;
public:
    SegmentTree() {}

    //m=size, f=[](M a,M b){return ;}
    // size : m
    SegmentTree(int m, const Func f, const Monoid &unity) {
        build(m, f, unity);
    }

    SegmentTree(const std::vector<Monoid>& v, const Func f, const Monoid &unity) {
        build(v, f, unity);
    }

    void build(int m, const Func f, const Monoid &unity) {
        F = f;
        UNITY = unity;
        n = 1; while (n < m) n <<= 1;
        node.resize(n * 2 - 1, UNITY);
    }

    void build(const std::vector<Monoid>& v, const Func f, const Monoid &unity) {
        F = f;
        UNITY = unity;
        int sz = v.size();
        n = 1; while (n < sz) n <<= 1;
        node.resize(n * 2 - 1, UNITY);
        REP(i, sz) node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--) node[i] = F(node[2 * i + 1], node[2 * i + 2]);
    }

    void update(int x, Monoid val) {
        if (x >= n || x < 0) return;
        x += n - 1;
        node[x] = val;
        while (x > 0) {
            x = (x - 1) >> 1;
            node[x] = F(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    // [a,b)
    Monoid get(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return UNITY;
        if (a <= l && r <= b) return node[k];
        Monoid vl = get(a, b, 2 * k + 1, l, (r - l) / 2 + l);
        Monoid vr = get(a, b, 2 * k + 2, (r - l) / 2 + l, r);
        return F(vl, vr);
    }

    Monoid operator[](int x)const {
        return node[n + x - 1];
    }

    int size() {
        return n;
    }

    void print() {
        REP(i, n) {
            std::cout << i << "\t: " << node[n + i - 1] << std::endl;
        }
    }
};

int main() {
    int n, m; cin >> n >> m;
    string s; cin >> s;
    const int inf = 1e9 + 1;
    SegmentTree<int> seg(n + 1, [](int a, int b) {return min(a, b); },inf);
    seg.update(n, 0);
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '1') continue;
        int rm = seg.get(i + 1, min(n, i + m) + 1);
        if (rm == inf) {
            puts("-1");
            return 0;
        }
        seg.update(i, rm + 1);
    }
    int now = 0;
    while (now < n) {
        FOR(i,1, m+1) {
            if (seg[now] - 1 == seg[now + i]) {
                now += i;
                cout << i << " ";
                break;
            }
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstring>
using namespace std;

int mp[110][110];
int sa[10010];
int h, w, n;

int main() {
	while (cin >> h >> w) {
		cin >> n;
		memset(mp, 0, sizeof(mp));
		for (int i = 1; i <= n; i++)
			cin >> sa[i];
		int ii = 0, jj = 0, cc = 1;
		int cas = h * w;
		while (cas--) {
			while (sa[cc] == 0) {
				cc++;
			}
			mp[ii][jj] = cc;
			sa[cc]--;;
			if (jj % 2 == 0) {
				ii++;
				if (ii >= w) {
					ii = w - 1;
					jj++;
				}
			}else {
				ii--;
				if (ii < 0) {
					ii = 0;
					jj++;
				}
			}
		}
		for (int j = 0; j < h; j++) {
			for (int i = 0; i < w; i++) {
				if (i)
					cout << " " << mp[i][j];
				else
					cout << mp[i][j];
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 384
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

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

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;
// }}}

int N;
ll a[200000];

bool isOk(ll a, ll b)
{
    bool ret = true;
    while(a != 0 && b != 0){
        ll aa = a & 1;
        ll bb = b & 1;
        if(aa == bb && aa == 1){
            ret = false;
            break;
        }
        a >>= 1;
        b >>= 1;
    }
    return ret;
}

void init()
{
}

void solve()
{
    ll ans = 0;
    ll current = 0;
    int r = -1;
    REP(l, N){
        while(r < N-1 && isOk(current, a[r+1])){
            current ^= a[r+1];
            ans += (r+1) - l + 1;
            r++;
        }
        if(r == N-1) break;
        current &= ~a[l];
    }

    cout << ans << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    REP(i, N) cin >> a[i];
    solve();
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 1792
import sys
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b
# dp[i][0] から dp[i + 1][1] への遷移
# dp[i][0] から dp[i + 1][2] への遷移
# dp[i][1] から dp[i + 1][0] への遷移
# dp[i][1] から dp[i + 1][2] への遷移
# dp[i][2] から dp[i + 1][0] への遷移
# dp[i][2] から dp[i + 1][1] への遷移
# 各 j (= 0, 1, 2) と各 k (= 0, 1, 2) に対して、j ≠ k ならば
# chmin(dp[i + 1][k], dp[i [j] + lst_happiness[i][k])
for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])
print(ans)

Measured memory_bytes: 50104
#include<stdio.h>
#include<string.h>

int main(void){
char s[100];
char t[4];
int len;
int i;
scanf("%s",s);
len=strlen(s);
if(len==2){
printf("%s",s);
}else{
t[0]=s[2];
t[1]=s[1];
t[2]=s[0];
printf("%s",t);
}
return 0;
}

Measured memory_bytes: 128
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    C = readline().strip()
    print(chr(ord(C) + 1))
    
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 61732
"""
被りなし
cmb(n-2,k)
被りあり2子使うなら
  x,x,x, A, y,y,y,y, A, z,z,z
cmb(n-2,k-2)
被りあり、１つだけ使うなら。。。
  cmb(n-2,k-1) * 2 # y使うかもしれないけーす
  cmb(count(x) + count(z), k-1) # y使わないケース（２倍カウントしてる）
"""
N = int(input())
A = list(map(int, input().split()))
dup = sum(A) - N*(N+1)//2
idx = []
for i in range(len(A)):
  if A[i] == dup:
    idx.append(i)
    
countXZ = N - idx[1] + idx[0]
### nCr mod
# https://qiita.com/derodero24/items/91b6468e66923a87f39f
mod = 10**9+7 #出力の制限
NMAX = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NMAX + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def cmb(n, r, m=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % m

# solve
print(N) # k=1
for k in range(2,N+1):
  wk = cmb(N-1,k)
  wk += cmb(N-1,k-2)
  wk += cmb(N-1,k-1) * 2
  wk -= cmb(countXZ, k-1)
  #print(cmb(N-1,k), cmb(N-1,k-2), cmb(N-1,k-1) * 2, cmb(countXZ, k-1))
  print(wk % mod)
print(1) # k=N+1

Measured memory_bytes: 25540
N,x = map(int,input().split())
a = list(map(int,input().split()))
i = 0
answer = 0
if a[0] > x:
  answer = a[0] - x
  a[0] = x
for i in range(N-1):
    if a[i] + a[i+1] > x:
        answer += a[i] + a[i+1] - x
        a[i+1] = x - a[i]
print(answer)


Measured memory_bytes: 14252
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long
const ll maxn = 3000;
const ll INF = (ll)1 << 50;
using namespace std;
int head[maxn];
int n;
struct Edge{
	ll f, t, next, dis;
}edge[maxn];

ll cnt = 1;
inline void addedge(ll f, ll t, ll v){
	edge[++cnt].next = head[f];
	edge[cnt].f = f;
	edge[cnt].t = t;
	edge[cnt].dis = v;
	head[f] = cnt;
}
ll cost = 0;
inline void adde(ll f, ll t, ll v){
	addedge(f, t, v);
	addedge(t, f, v);
	cost += v;
}

struct Nod{
	ll pos, dis;
	inline bool operator < (const Nod &mr) const {return dis > mr.dis;}
};

ll dis[maxn];
inline ll dijkstra(ll S, ll T){
	priority_queue <Nod> q;
	for (ll i = 1; i <= n; i++) dis[i] = INF;
	dis[S] = 0;
	q.push((Nod){S, dis[S]});
	while (!q.empty()){
		Nod cur = q.top(); q.pop();
		if (cur.pos == T) return cur.dis;
		if (cur.dis > dis[cur.pos]) continue;
		for (ll i = head[cur.pos]; i; i = edge[i].next){
			if (dis[edge[i].t] > cur.dis + edge[i].dis)
				q.push((Nod){edge[i].t, dis[edge[i].t] = cur.dis + edge[i].dis});
		}
	}
	return INF;
}
struct D{
	ll f, t, v;
};
vector <D> vec;
bool cmp_v(D a, D b){
	return a.v < b.v;
}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++){
			int x; scanf("%d", &x);
			if (i < j) vec.push_back((D){i, j, x});
		}
	sort(vec.begin(), vec.end(), cmp_v);
	for (int i = 0; i < vec.size(); i++){
		ll f = vec[i].f, t = vec[i].t, v = vec[i].v;
		ll dij = dijkstra(f, t);
		if (v < dij) adde(f, t, v);
		else if (v > dij){puts("-1"); return 0;}
	}
	cout << cost << endl;
	return 0;
}


Measured memory_bytes: 1912
"""
a = int(input())
# スペース区切りの整数の入力
b, c = map(int, input().split())
# 文字列の入力
s = input()
# 出力
print(str(a+b+c) + " " + s)
"""


def main():
	while(1):
		N = input().split() 
		if N[0] == "#":
			break
		y = int(N[1])
		m = int(N[2])
		d = int(N[3])
		if y >= 32:
			print("? {} {} {}".format(y-30,m,d))
		if y < 31:
			print("{} {} {} {}".format(N[0],y,m,d))
		if y==31:
			if m>=5:

				print("? {} {} {}".format(y-30,m,d))
			else:
				print("{} {} {} {}".format(N[0],y,m,d))


if __name__ == '__main__':
    main()


Measured memory_bytes: 5620
#include<stdio.h>
#include<stdlib.h>
#define N 10000

int main(){
  int n,i,j,count[N+1];
  unsigned short *in,*out;
  scanf("%d",&n);

  in=malloc(sizeof(short)*n+1);
  out=malloc(sizeof(short)*n+1);
  
  for(i=0;i<=N;i++){
    count[i]=0;
  }
  
  for(i=1;i<=n;i++){
    scanf("%d",&in[i]);
    count[in[i]]++;
  }
 
  for(i=1;i<=N;i++){
    count[i]=count[i]+count[i-1];
  }
 
  for(j=1;j<=n;j++){
    out[count[in[j]]]=in[j];
    count[in[j]]--;
  }
  for(i=1;i<=n;i++){
    if(i>1)printf(" ");
    printf("%d",out[i]);
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 9604
#include <iostream>
#include <cfenv>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <limits>

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

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

    vector<int> a(n,0);
    rep(i,n){
        cin >> a[i];
    }

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

    rep(i, n-1){
        if (a[i] == a[i+1]){
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
}

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

int main()
{
    list<char> z; list<char>::iterator itr;
    list<char>::reverse_iterator it;
    string s;   cin>>s;
    for(int i=0; i<s.size(); i++)
        z.push_back(s[i]);
    int x=0;
    int q; cin>>q;
    while(q--)
    {
        int t;
        cin>>t;
        if(t==1) x^=1;
        else
        {
            int f; char c;
            cin>>f>>c;
            if(f==1 && x==1) z.push_back(c);
            else if(f==1 && x==0) z.push_front(c);
            else if(f==2 && x==0) z.push_back(c);
            else if(f==2 && x==1) z.push_front(c);
        }
    }
    if(x==1)
        for(it=z.rbegin(); it!=z.rend(); it++)
            cout<<*it;
    else
        for(itr=z.begin(); itr!=z.end(); itr++)
            cout<<*itr;
    cout<<endl;
    return 0;
}


Measured memory_bytes: 9984
N = int(input())

T = 0
X = 0
Y = 0
for i in range(N):
    t, x, y = map(int, input().split())
    if ((t - T) + abs(x-X) + abs(y-Y))%2 == 1 or (t - T) < abs(x-X) + abs(y-Y):
        print("No")
        break
else:
    print("Yes")

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<string>
#include<cstdio>
#include<queue>
#include<functional>
#include <tuple>
#include<iomanip>
#include<stack>
#include<cmath>
#define ll long long
using namespace std;
int main() {
	ll n, x[8], y[8], a=1; cin >> n;
	double sum = 0;
	for (int i = 0; i < n; ++i,a*=i) cin >> x[i] >> y[i];
	vector<int>data(n);
	for (int i = 0; i < n; ++i) data[i] = i;
	do {
		for (int i = 0; i < n - 1; ++i) sum += sqrt(pow(x[data[i]] - x[data[i + 1]], 2) + pow(y[data[i]] - y[data[i + 1]], 2));
	}while (next_permutation(data.begin(), data.end()));
	printf("%.7f\n", sum / a);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n, sum;
int a[25], b[25], c[25];
int main() {
	cin >> n;
	for (int i=1; i<=n; i++) cin >> a[i];
	for (int i=1; i<=n; i++) cin >> b[i];
	for (int i=1; i<=n-1; i++) cin >> c[i];
	for (int i=1; i<=n; i++) {
		sum += b[a[i]];
		if (i > 1 && a[i] - a[i-1] == 1) sum += c[a[i-1]];
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323
#define ll long long int
#define vi vector <int>
#define vl vector <ll>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define MOD 1000000007
ll power(ll a, ll b) { //a^b
	ll res = 1;
	while (b > 0) {
		if (b & 1) {res = (res * a); b--;}
		a = (a * a);
		b >>= 1;
	}
	return res;
}
ll n;
ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a % b);}



int main() {
	
	ll n,k;
	cin>>n>>k;
	vector <ll> a(n);
	for(ll i=0;i<n;i++)
		cin>>a[i];
	vector <ll> dp(n);
	dp[0]=0;
	for(ll i=1;i<n;i++){
		dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
		for(ll j=2;(j<=k&&i-j>=0);j++)
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
	}
	cout<<dp[n-1]<<"\n";
}


Measured memory_bytes: 4844
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <tuple>
#include <algorithm>

using namespace std;

int main(){

    int K;
    string S;
    cin >> K;
    cin >> S;

    for(int i=0;i<S.size();i++){
        if(i == K){
            cout << "...";
            break;
        }
        cout << S[i];
    }

    cout << endl;
    return 0;
}


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

int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        int* a = new int[n];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        long long max = a[0];
        for (int i = 0; i < n; i++) {
            long long sum = 0;
            for (int j = i; j < n; j++) {
                sum += a[j];
                if (max < sum) {
                    max = sum;
                }
            }
        }
        cout << max << endl;
        delete[] a;
    }
}

Measured memory_bytes: 0
#include <stdio.h>

void calculator (int, int, char);

int main (void)
{
	int a[10000], b[10000];
	char op[10000];
	int i=0;

	for(i=0;;i++){
		scanf("%d %c %d", &a[i], &op[i], &b[i]);
		if(op[i]=='?') break;
	}

	for(i=0;;i++){
		if(op[i]=='?') break;
		calculator(a[i], b[i],op[i]);
	}

	return 0;
}

void calculator (int a, int b, char op)
{
	if (op!='?'){
		if(op=='+'){
			printf("%d\n", a+b);
		} else if(op=='-'){
			printf("%d\n", a-b);
		} else if(op=='*'){	
			printf("%d\n", a*b);
		} else if(op=='/'){
			printf("%d\n", a/b);
		}
	}

	return ;
}

Measured memory_bytes: 616
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <time.h>

#define loop(i, num)  for (int i = 0; i < num; i++)

using namespace std;

int n, ans;

vector<int> nums;

int main() {
    
    cin >> n;
    
    nums.resize(n);
    
    loop (i, n) {
        
        cin >> nums[i];
        
    }
    
    for (int i = 0; i < n - 1; i++) {
        
        if (nums[i] == i + 1) {
            
            swap(nums[i], nums[i + 1]);
            
            ++ans;
            
        }
        
    }
    
    if (nums[n - 1] == n) {
        
        ++ans;
        
    }
    
    cout << ans << endl;
    
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
int main()
{
    char s[100];
    int n,k,len,i;
    scanf("%d%d",&n,&k);
    scanf("%s",s);
    len = strlen(s);
    for(i=0;i<len;i++)
    {
        if(i+1==k)
        {
            s[i]=s[i]+32;
        }
    }
    printf("%s\n",s);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(c) (c).begin(), (c).end()
#define mp(a, b) make_pair(a, b)
const int inf = 1 << 28;

int N;
vector<string> in;
vector<pair<int, bool> > var;

bool pruning(int used, int sum, int k){
    if(sum == 0)return false;
    int mask = (1 << 10) - 1, sig = sum < 0? -1: 1;
    for(int i=k; i<(int)var.size(); ++i){
        int j = 0 < var[i].first * sig? __builtin_popcount(used & (~used-1)): 31 - __builtin_clz(mask ^ used);
        sum += j * var[i].first;
        used |= 1 << j;
    }
    return sig < 0? sum < 0: 0 < sum;
}

int dfs(int used, int sum){
    int k = __builtin_popcount(used);
    if((int)var.size() <= k)return sum == 0;
    if(pruning(used, sum, k))return 0;
    int res = 0;
    rep(i, 10){
        if(used >> i & 1 || (!i && var[k].second))continue;
        res += dfs(used | 1 << i, sum + i * var[k].first);
    }
    return res;
}

int solve(){
    var.assign(26, mp(inf, false));
    rep(i, N)for(int j=(int)in[i].size()-1, d=1; j>=0; --j, d*=10){
        if(var[in[i][j] - 'A'].first == inf)var[in[i][j] - 'A'].first = 0;
        var[in[i][j] - 'A'].first += i != N-1? d: -d;
        if(j == 0 && (int)in[i].size() != 1)var[in[i][j] - 'A'].second = true;
    }
    var.erase(remove_if(all(var), [](pair<int, bool> p){return p.first == inf;}), var.end());
    sort(all(var), [](const pair<int, bool>& a, const pair<int, bool>& b){return abs(b.first) < abs(a.first);});
    return 10 < (int)var.size()? 0: dfs(0, 0);
}

int main(){
    while(cin >> N, N){
        in.assign(N, "");
        rep(i, N)cin >> in[i];
        cout << solve() << '\n';
    }
    return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define COUT(x) cout << (x) << endl
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */


int main() {
    int x, a;
    cin >> x >> a;
    if(x < a) COUT(0);
    else COUT(10);
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin >> N;
    vi A(N);
    cin >> A;
    int ans = 0;
    int l = 0;
    rep(i, 1, N) {
        if (A[i - 1] < A[i]) {
            chmax(ans, i - l - 1);
            l = i;
        }
    }
    if (l != N - 1) {
        chmax(ans, N - l - 1);
    }
    cout << ans << endl;
    return (0^_^0);
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int N=190;
int n,m,sm[N][N],dp[2][N][N][N];
char ch[N][N];
bool chk(int x1,int y1,int x2,int y2)
{
  int s=sm[x2][y2]-sm[x2][y1-1]-sm[x1-1][y2]+sm[x1-1][y1-1];
  return (!s)||s==(x2-x1+1)*(y2-y1+1);
}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
    scanf("%s",ch[i]+1);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)sm[i][j]=sm[i][j-1]+(ch[i][j]=='.');
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)sm[i][j]+=sm[i-1][j];
  for(int i=1;i<=n;i++)for(int j1=1;j1<=m;j1++)for(int j2=j1;j2<=m;j2++)
  {
    int l=i,r=n,ans=i-1;
    while(l<=r)
    {
      int mid=l+r>>1;
      if(chk(i,j1,mid,j2))ans=mid,l=mid+1;else r=mid-1;
    }
    dp[0][i][j1][j2]=ans;
  }
  if(dp[0][1][1][m]==n){puts("0");return 0;}
  bool u=1,v=0;
  for(int t=1;t<=16;t++,swap(u,v))
  {
    for(int i=1;i<=n;i++)
      for(int j1=1;j1<=m;j1++)
        for(int j2=j1;j2<=m;j2++)
        {
          int d=dp[v][dp[v][i][j1][j2]+1][j1][j2];
          if(dp[v][i][j1][j2]==n)
          { dp[u][i][j1][j2]=n;continue;}
          int l=j1,r=j2-1;
          while(l<=r)
          {
            int mid=l+r>>1;
            int t1=dp[v][i][j1][mid],t2=dp[v][i][mid+1][j2];
            d=Mx(d,Mn(t1,t2));
            if(t1>=t2)l=mid+1; else r=mid-1;
          }
          dp[u][i][j1][j2]=d;
        }
    if(dp[u][1][1][m]==n){printf("%d\n",t);return 0;}
  }
  return 0;
}


Measured memory_bytes: 53504
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"sort"
)

// github.com/EndlessCheng/codeforces-go
func run(_r io.Reader, _w io.Writer) {
	out := bufio.NewWriter(_w)
	defer out.Flush()
	buf := make([]byte, 4096)
	_i := len(buf)
	rc := func() byte {
		if _i == len(buf) {
			_r.Read(buf)
			_i = 0
		}
		b := buf[_i]
		_i++
		return b
	}
	r := func() (x int) {
		b := rc()
		for ; '0' > b; b = rc() {
		}
		for ; '0' <= b; b = rc() {
			x = x*10 + int(b&15)
		}
		return
	}
	type pair struct{ l, r, i int }

	n, q := r(), r()
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		a[i] = r()
	}
	qs := make([]pair, q)
	for i := range qs {
		qs[i] = pair{r(), r(), i}
	}
	sort.Slice(qs, func(i, j int) bool { return qs[i].r < qs[j].r })

	tree := make([]int, n+1)
	add := func(i int, val int) {
		for ; i <= n; i += i & -i {
			tree[i] += val
		}
	}
	query := func(l, r int) (s int) {
		for ; r > l; r &= r - 1 {
			s += tree[r]
		}
		for ; l > r; l &= l - 1 {
			s -= tree[l]
		}
		return
	}

	ans := make([]int, q)
	posR := make([]int, n+1)
	i := 1
	for _, q := range qs {
		for ; i <= q.r; i++ {
			if p := posR[a[i]]; p > 0 {
				add(p, -1)
			}
			add(i, 1)
			posR[a[i]] = i
		}
		i = q.r + 1
		ans[q.i] = query(q.l-1, q.r)
	}
	for _, v := range ans {
		Fprintln(out, v)
	}
}

func main() { run(os.Stdin, os.Stdout) }


Measured memory_bytes: 36060
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    ll k;
    cin >> s >> k;
    vll a;
    rep(i, sz(s)) {
        if (i == 0) a.pb(1);
        else if (s[i-1] == s[i]) a.back()++;
        else a.pb(1);
    }
    ll ans = 0;
    if (sz(a) == 1) ans = (a[0] * k) / 2;
    else if (sz(a) == 2) ans = (a[0] / 2 + a[1] / 2) * k;
    else {
        rep(i, sz(a)) {
            if (i == 0 || i == sz(a) - 1) continue;
            ans += a[i] / 2;
        }
        ans *= k;
        if (s[0] == s.back()) {
            ans += a[0] / 2 + a.back() / 2;
            ans += (k-1) * ((a[0] + a.back()) / 2);
        } else {
            ans += (a[0] / 2 + a.back() / 2) * k;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
    int n,i,max=0,sum=0;
    char s[101];
    scanf("%d",&n);
    scanf("%s",s);
    for(i=0;i<n;i++){
        if(s[i]=='I')
            sum++;
        if(s[i]=='D')
            sum--;
        if(max<sum)
            max=sum;
    }
    printf("%d\n",max);
    return 0;
}

Measured memory_bytes: 1708
#include <iostream>
#include <string>
using namespace std;

int main() {

	int n, key;

	cin >> n;

	key = n % 10;

	if (key == 3) cout << "bon";
	else if (key == 0 || key == 1 || key == 6 || key == 8) cout << "pon";
	else cout << "hon";

	return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

const ll mod=1e9+7;

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<max(0,min(b,d)-max(a,c))<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	double a,b,a1,b1;
	cin>>a>>b;
	a1=a/.08;
	b1=b/.1;

	if((b1<=a1&&a1<=b1+9)||a1==b1){
		cout<<ceil(max(a1,b1))<<endl;
	}
	else if(a1<=b1&&b1<=a1+12){
		cout<<ceil(max(a1,b1))<<endl;
	}
	else{
		cout<<-1<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>

using namespace std;

char str[801];
int temp;

string delque(const string&);
string revstr(const string&);
string Cipher();
string String();
char Letter();

int main()
{
  while(1){
    temp = 0;
    fgets(str,801,stdin);
    if(str[0] == '.' && str[1] == '\n')
      break;
    cout << delque(Cipher()) << endl;
  }
  return 0;
}

string delque(const string& instr)
{
  string retst;
  char st[801];
  strcpy(st,instr.c_str());
  for(int i = 0;st[i] != '\0';i++){
    if(st[i] == '?')
      st[i] = 'A';
  }
  retst = st;
  return retst;
}

string revstr(const string& instr)
{
  int i;
  string retstr;
  char st[801],ret[801];
  strcpy(st,instr.c_str());
  for(i = 0;st[i] != '\0';i++){}
  i--;
  for(;i >= 0;i--){
    retstr += st[i];
  }
  return retstr;
}

string Cipher()
{
  string ret = String();
  while(1){
    if(str[temp] == '\n'){
      break;
    } else if(str[temp] == ']'){
      break;
    } else {
      ret += String();
    }
  }
  return ret;
}

string String()
{
  int i;
  string ret;
  char rev[801];
  if(str[temp] == '['){
    temp++;
    ret += revstr(Cipher());
    if(str[temp] == ']'){
      temp++;
    }
  } else {
    ret += Letter();
  }
  return ret;
}

char Letter()
{
  char ret;
  if(str[temp] == '+'){
    temp++;
    ret = Letter() + 1;
    if(ret == '?' + 1){
      ret--;
    } else if(ret > 'Z'){
      ret -= 'Z' - 'A' + 1;
    }
  } else if(str[temp] == '-'){
    temp++;
    ret = Letter() - 1;
    if(ret == '?' - 1){
      ret++;
    } else if(ret < 'A'){
      ret += 'Z' - 'A' + 1;
    }
  } else if((str[temp] >= 'A' && str[temp] <= 'Z' ) || str[temp] == '?'){
    ret = str[temp++];
  }
  return ret;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
    
int main() {
  for (int i = 0; ; i++) { 
   int X, Y;
   string op;
   cin >> X >> op >> Y;
    
   if (op == "?") {
    break;
    }
 
   else if (op == "+") {
     X += Y;
     cout << X << endl;
    }
 
   else if (op == "-") {
     X -= Y;
     cout << X << endl;
    }
    
   else if (op == "*") {
     X *= Y;
     cout << X << endl;
    }
 
   else if (op == "/") {
     X /= Y;
     cout << X << endl;
    }
 
  }
   return 0;
  
  
}


Measured memory_bytes: 3132
from collections import deque

H, W = map(int, input().split())
S = [0]*H
for i in range(H):
    S[i] = input()
# print(H, W, S)


def is_inside(w, h, W, H):
    if w >= 0 and w < W and h >= 0 and h < H:
        return True
    return False

def solve(sh, sw):
    T = [[0]* W for h in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                T[i][j] = -1
    if T[sh][sw] == -1:
        return T
    V = deque([(sh, sw)])
    T[sh][sw] = -2
    while len(V) != 0:
        v = V.popleft()
        h = v[0]
        w = v[1]
        # print(h, w)
        t = T[h][w]
        if t == -2:
            t = 0
        if is_inside(h - 1, w, H, W):
            if T[h - 1][w] == 0:
                T[h - 1][w] = t + 1
                V.append((h - 1, w))
        if is_inside(h + 1, w, H, W):
            if T[h + 1][w] == 0:
                T[h + 1][w] = t + 1
                V.append((h + 1, w))
        if is_inside(h, w - 1, H, W):
            if T[h][w - 1] == 0:
                T[h][w - 1] = t + 1
                V.append((h , w - 1))
        if is_inside(h, w + 1, H, W):
            if T[h][w + 1] == 0:
                T[h][w + 1] = t + 1
                V.append((h , w + 1))
    # print(sh, sw, T)
    return T


ans = 0

for h in range(H):
    for w in range(W):
        T = solve(h, w)
        distance = 0
        for i in range(H):
            for j in range(W):
                d = T[i][j]
                distance = max(distance, d)
        ans = max(distance, ans)

print(ans)


Measured memory_bytes: 60252
{-# LANGUAGE BangPatterns #-}

module Main where

import Data.Char
import Data.List
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Control.Applicative
import Text.Printf


readInt :: IO Int
readInt = read <$> (input `seq` input)
    where input = do
            !c <- getChar
            if isDigit c || c == '-'
                then (c :) <$> input
                else return []

prints :: Show a => [a] -> IO ()
prints as = putStrLn $ concat $ intersperse " " $ map show as

main = do
    [n,m] <- replicateM 2 readInt
    a <- replicateM n (replicateM m readInt)
    b <- replicateM m readInt
    forM_ [0..n-1] $ \i -> print (sum $ zipWith (*) (a !! i) b)


Measured memory_bytes: 8236
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long T = sc.nextLong();
    long ans = T;
    long[] t = new long[N];
    for(int i = 0; i < N; i++) {
      t[i] = sc.nextLong();
    }
    for(int i = 0; i < N - 1; i++) {
      ans += Math.min(T, t[i + 1] - t[i]);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 67212