akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Main {

    public static void main(String[] args) throws Exception {

        try {

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            List<String> input = Arrays.asList(br.readLine().split(" "));
            List<Integer> numbers = new ArrayList<>();

            for (String s : input) {
                numbers.add(Integer.parseInt(s));
            }

            int result = numbers.get(0) * numbers.get(1);
            if (numbers.get(0) > 9 || numbers.get(1) > 9) {
                result = -1;
            }

            System.out.println(result);
        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(0);
        } catch (final Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

Measured memory_bytes: 22228
import sys, fractions, functools
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

def resolve():
    N, M = LI()
    a = LI()

    a_half = [i//2 for i in a]
    a_half_lcm = lcm_list(a_half)
    has_scm = not 0 in [a_half_lcm//i%2 for i in a_half]

    if has_scm:
        print((M-a_half_lcm)//(2*a_half_lcm)+1)
    else:
        print(0)

if __name__ == '__main__':
    resolve()

Measured memory_bytes: 16272
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
int R,C;
bool Out(int x,int y){
    return x&&x!=R&&y&&y!=C;
}
int get(int x,int y){
    if(!y)return x;
    if(x==R)return R+y;
    if(y==C)return R+C+R-x;
    return R*2+C+C-y;
}
int stk[SIZE],sn;
int main(){
    VPII pp;
    RII(R,C);
    DRI(N);
    REP(i,N){
        DRII(x1,y1);
        DRII(x2,y2);
        if(Out(x1,y1))continue;
        if(Out(x2,y2))continue;
        pp.PB(MP(get(x1,y1),i));
        pp.PB(MP(get(x2,y2),i));
    }
    sort(ALL(pp));
    REP(i,SZ(pp)){
        if(sn&&stk[sn-1]==pp[i].S)sn--;
        else stk[sn++]=pp[i].S;
    }
    puts(sn?"NO":"YES");
    return 0;
}


Measured memory_bytes: 2420
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    a, b, x = MAP()

    print(b//x - (a-1)//x)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10056
n = int(input())
a = list(map(int, input().split()))

def gcd(x, y):
    x, y = max(x, y), min(x, y)
    while x%y > 0:
        x, y = y, x%y
    return y

a = sorted(a)
ans = [gcd(a[0], a[1]), a[0]]
for i in range(2, n):
    ans_0, ans_1 = ans
    ans_0_new = gcd(ans_0, a[i])
    ans_1_new = max(ans_0, gcd(ans_1, a[i]))
    ans = [ans_0_new, ans_1_new]
ans_2 = a[1]
for i in range(2, n):
    ans_2 = gcd(ans_2, a[i])
print(max(ans+[ans_2]))


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

void trace(vector<int> &a,int N){
  for(int i=0;i<N;i++){
    if(i){
      cout<<" ";
    }
    cout<<a[i];
  }
  cout<<endl;
  
}

int selectionsort(vector<int> &v,int N){
  int cnt=0;
  for(int i=0;i<N;i++){
    int minj=i;
    for(int j=i;j<N;j++){
      if(v[j]<v[minj]){
        minj=j;
      }
    }
    if(i !=minj){
      swap(v[i],v[minj]);
      cnt++;
    }
  }
  return cnt;
}
int main() {
  string n;
  cin>>n;
  for(int i=0;i<3;i++){
    if(n[i]=='1'){
      n[i]='9';
    }
    else{
      n[i]='1';
    }
  }
  cout<<n<<endl;
}

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

//--------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX/3

//--------------------------------------------
const double EPS = 1e-14;
const double PI  = acos(-1.0);

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

int main(){
  int n, k;
  int x;
  int sum = 0;

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

  REP (i, n) {
    scanf("%d",&x);
    sum += 2 * min(x, k - x);
  }

  printf("%d\n",sum);
}


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

int dp[310][310], sum[310];
int C[310][310];

int main () {
	int n, k, mod; cin >> n >> k >> mod;
	C[0][0] = 1;
	for (int i = 1; i <= n + 1; i++) {
		for (int j = 0; j <= i; j++) {
			C[i][j] = (C[i - 1][j] + (j ? C[i - 1][j - 1] : 0)) % mod;
		}
	}
	for (int i = 0; i <= k; i++) {
		dp[1][i] = 1;
	}
	for (int i = 2; i <= n + 1; i++) {
		memset(sum, 0, sizeof(sum));
		for (int j = k - 1; j >= 0; j--) {
			for (int t = 1; t < i; t++) {
				(sum[t] += dp[t][j + 1]) %= mod;
			}
			for (int t = 1; t < i; t++) {
				(dp[i][j] += 1ll * dp[i - t][j] * sum[t] % mod * C[i - 2][t - 1] % mod) %= mod;
			}
		}
	}
	printf("%d\n", dp[n + 1][0]);
	return 0;
}


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

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

pair<pair<lint, lint>, lint> ext_gcd(lint a, lint b){
    if(b == 0) return {{1, 0}, a};
    else if(a < b){
        auto p = ext_gcd(b, a);
        return {{p.fi.se, p.fi.fi}, p.se};
    }
    else{
        auto p = ext_gcd(b, a%b);
        lint s = p.fi.fi, t = p.fi.se;
        return {{t, s - a/b * t}, p.se};
    }
}

int main(){
    using pll = pair<lint, lint>;
    lint a, b, d;
    while(scanf("%lld%lld%lld", &a, &b, &d) && a){
        lint s, t, g;
        auto p = ext_gcd(a, b);
        tie(s, t) = p.fi; g = p.se;
        s *= d / g; t *= d / g;
        pair<pll, pll> ans = {{INF, INF}, {INF, INF}};
        lint A = a / g, B = b / g;
        lint L = min(-1.0*s/B, 1.0*t/A), R = max(-1.0*s/B, 1.0*t/A);
        For(k, L-5, R+5){
            lint x = abs(B*k + s), y = abs(-A*k + t);
            chmin(ans, {{x+y, a*x+b*y}, {x, y}});
        }
        printf("%lld %lld\n", ans.se.fi, ans.se.se);
    }
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
const int MAX=4e5+10;
template <typename T> inline  void read(T &a){
      T w=1;a=0;
	  char ch=getchar();
	  for(;!isdigit(ch);ch=getchar()){
	      if(ch == '-') w=-1;
	  }
	  for(;isdigit(ch);ch=getchar()){
	      a=(a<<3)+(a<<1)+(ch^48);
	  }
	  a*=w;
}
int n;
int a[MAX];

int ck(int k){
    for(register int i=0;i<n;++i){
	    if((a[n+i] <= k && a[n+i+1]<=k) || (a[n-i]<=k && a[n-i-1]<=k)) return 1;
		if((a[n+i]>k && a[n+i+1]>k) || (a[n-i]>k && a[n-i-1]>k)) return 0;
	}
	return a[1]<=k;
}

int main(){
		read(n);
		for(register int i=1;i<(n*2);++i){
		    read(a[i]);
		}
	    int l=1,r=(n<<1)-1;
		while(l<r){
		   int mid=(l+r)>>1;
		   if(ck(mid)) r=mid;
		   else l=mid+1;
		}
		cout<<l;

}

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

using namespace std;

int main(){
    int n,k,r,s,p;
    cin >> n >> k >> r >> s >> p;
    string t;
    cin >> t;
    int ans=0;
    vector<pair<int,char>> b(n);
    for(int i=0;i<n;i++){
        if(i<k){
            if(t[i]=='r'){
                ans+=p;
                b[i].first=1;
                b[i].second='p';
            }
            else if(t[i]=='s'){
                ans+=r;
                b[i].first=1;
                b[i].second='r';
            }
            else if(t[i]=='p'){
                ans+=s;
                b[i].first=1;
                b[i].second='s';
            }
        }
        else{
            if(t[i]=='r'){
                if(b[i-k].first==0 || b[i-k].second!='p'){
                    ans+=p;
                    b[i].first=1;
                    b[i].second='p';
                }
            }
            else if(t[i]=='s'){
                if(b[i-k].first==0 || b[i-k].second!='r'){
                    ans+=r;
                    b[i].first=1;
                    b[i].second='r';
                }
            }
            else if(t[i]=='p'){
                if(b[i-k].first==0 || b[i-k].second!='s'){
                    ans+=s;
                    b[i].first=1;
                    b[i].second='s';
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1280
# E - Crested Ibis vs Monster
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))


Measured memory_bytes: 43116
#include <stdio.h>
int main(void) 
{
    int N, M, s[100], c[100], i,t, number;
    int num[40] = {0};
    number = 0;

    scanf("%d%d", &N, &M);

    for (i = 1; i <= M; i++){
        scanf("%d%d", &s[i], &c[i]);
    }

    for (i = 1; i <= M; i++){
        if (N != 1 && s[i] == 1 && c[i] == 0)
        number = -1;
    }

    for (i = 1; i <= M; i++){
        for (t = 1; t <= M; t++){
            if (s[i] == s[t] && c[i] != c[t])
                number = -1;
        }
    }

    if (number == -1)
        printf("%d", number);    
    
    else{
        for (i = 1; i <= M; i++){
            switch (s[i]){
                case 1: num[1] = c[i]; break;
                case 2: num[2] = c[i]; break;
                case 3: num[3] = c[i]; break;
            }
        }
    if (N == 2 && num[1] == 0)
        num[1] = 1;
    if (N == 3 && num[1] == 0)
        num[1] = 1;
        
    if (N == 1)
        printf("%d", num[1]);
    else if (N == 2)
        printf("%d", 10*num[1] + num[2]);
    else 
        printf("%d", 100*num[1] + 10*num[2] + num[3]);
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;

vector <pip> from[100010];
vector <ppp> qq[100010];
int fa[100010][17], dep[100010], dis[100010];
int sum[100010], sss[100010];
int ans[100010];

void dfs(int x, int last) {
	fa[x][0] = last;
	for (int j = 1; j < 17; j++) {
		fa[x][j] = fa[fa[x][j - 1]][j - 1];
	}
	for (int i = 0; i < from[x].size(); i++) {
		int v = from[x][i].fi, w = from[x][i].se.se;
		if (v == last) continue;
		dep[v] = dep[x] + 1, dis[v] = dis[x] + w;
		dfs(v, x);
	}
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	int tmp = dep[x] - dep[y], cnt = 0;
	while (tmp) {
		if (tmp & 1) x = fa[x][cnt]; 
		tmp >>= 1, cnt++;
	}
	if (x == y) return x;
	for (int i = 16; i >= 0; i--) {
		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	}
	return fa[x][0];
}

void get_ans(int x, int last) {
	for (int i = 0; i < qq[x].size(); i++) {
		int id = qq[x][i].fi.fi, c = qq[x][i].fi.se, t1 = qq[x][i].se.fi, t2 = qq[x][i].se.se;
		ans[id] += t1 * sum[c] * t2 - t1 * sss[c];
	}
	for (int i = 0; i < from[x].size(); i++) {
		int v = from[x][i].fi, c = from[x][i].se.fi, w = from[x][i].se.se;
		if (v == last) continue;
		sum[c]++, sss[c] += w;
		get_ans(v, x);
		sum[c]--, sss[c] -= w;
	}
}

int main () {
	int n, q; scanf("%d%d", &n, &q);
	for (int i = 1; i < n; i++) {
		int x, y, c, d;
		scanf("%d%d%d%d", &x, &y, &c, &d);
		from[x].push_back(mp(y, mp(c, d)));
		from[y].push_back(mp(x, mp(c, d)));
	}
	dfs(1, 1);
	for (int i = 0; i < q; i++) {
		int x, y, c, d; scanf("%d%d%d%d", &c, &d, &x, &y);
		int lca = LCA(x, y);
		ans[i] = dis[x] + dis[y] - 2 * dis[lca];
		qq[x].push_back(mp(mp(i, c), mp(1, d)));
		qq[y].push_back(mp(mp(i, c), mp(1, d)));
		qq[lca].push_back(mp(mp(i, c), mp(-2, d)));
	}
	get_ans(1, 1);
	for (int i = 0; i < q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}


Measured memory_bytes: 30068
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
#define T int t = 0; cin >> t; while(t--)
#define b_e(a) a.begin(), a.end()
typedef long long ll;
typedef long double lld;
const ll mod = 998244353;
const ll mx = 6e5;

void input(){
    IOS;
    int s, w;
    cin >> s >> w;
    cout << ((w >= s) ? "unsafe" : "safe") << endl;
}
int main(){
    input();
    return 0;
} 


Measured memory_bytes: 3652
/*
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
*/

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

bool dp[40005];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    dp[0] = true;
    int n;
    cin >> n;
    rep(i,n){
    	int a;
    	cin >> a;
    	for(int j = 40000; j-a >= 0; j--){
    		dp[j] |= dp[j-a];
    	}
    }
    int q;
    cin >> q;
    rep(i,q){
    	int m;
    	cin >> m;
    	cout << (dp[m] ? "yes" : "no") << endl;
    }
    return 0;
}


Measured memory_bytes: 3212
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.next());
        sc.close();

        // 主処理
        int n = num % 10;
        String result = "hon";
        if (n == 3) {
            result = "bon";
        } else if (n == 0 || n == 1 || n == 6 || n == 8) {
            result = "pon";
        }

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 35664
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
typedef long long LL;
typedef long double Lf;
#define Rep(i,a,n)for(int i=(int)(a);i<(int)(n);i++)
#define rep(i,n)Rep(i,0,n)
#define Ma(x,y) ((x)>(y)?(x):(y))
#define mi(x,y) ((x)<(y)?(x):(y))
#define MOD 1000000007
int acs(const void* a, const void* b) { return *(int*)a - *(int*)b; } // 1,2,3,4
int des(const void* a, const void* b) { return *(int*)b - *(int*)a; } // 8,7,6,5
int cmp_char(const void* a, const void* b) { return *(char*)a - *(char*)b; } // a,b,c,d
int cmp_str(const void* a, const void* b) { return strcmp(*(const char**)a, *(const char**)b); } // aaa,aab
//snippet
#define N 100009

int group[N];

int root(int x) {
	if (group[x] == x)return x;
	group[x] = root(group[x]);
	return group[x];
}

void unite(int x, int y) {
	x = root(x);
	y = root(y);
	if (x == y)return;
	group[x] = y;
}

int main() {
	rep(i, N)group[i] = i;
	int n, m, p[N], x, y;
	scanf("%d%d", &n, &m);
	rep(i, n)scanf("%d", &p[i]);
	while (m--) {
		scanf("%d%d", &x, &y);
		unite(x - 1, y - 1);
	}
	int ans = 0;
	rep(i, n)if (root(i) == root(p[i] - 1))ans++;
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 2516
/** 
 *  Author : Parth Prajapati
 * 	Institute : Pandit Deendayal Petroleum University
**/
#include<bits/stdc++.h>

using namespace std; 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int m = n/500;
    m*=1000;
    int p = n-(m/2);
    p/=5;
    p*=5;
    cout<<(m+p);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    int s[m], c[m];
    for (int i = 0; i < m; i++) cin >> s[i] >> c[i];
    int p[] = {0, 10, 100, 1000};
    int lb = p[n-1], ub = p[n];
    for (int x = lb; x < ub; x++) {
        bool ok = true;
        string t = to_string(x);
        for (int i = 0; i < m; i++)
            if (t[s[i]-1] != c[i] + '0') {
                ok = false;
                break;
            }
        if (ok) { cout << x << endl; return 0; }
    }
    cout << "-1\n";
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 400005;
const int INF = 1001001001;
const int MOD = 1000000007;

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

    vector<int> A(N);
    for (auto &i : A) cin >> i;

    sort(A.begin(), A.end(), greater<int>());

    auto f = [](int n){
        int res = 1;
        while (res <= n) res *= 2;
        return res;
    };

    int ans = 0;
    map<int, int> count;
    for (auto &i : A) count[i]++;

    for (auto &i : A) {
        if (count[i] == 0) continue;
        int X = f(i);
        int n = X - i;
        if (count[n] == 0) continue;
        if (i == n && count[i] <= 1) continue;
        ans++;
        count[i]--;
        count[n]--;
    }

    cout << ans << endl;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    unordered_map<ll,int>mp;
    ll n;cin >>n;
    for (int i = 0; i < n; ++i) {
        ll a;cin >>a;
        if(mp[a]==1)mp[a]--;
        else mp[a]++;
    }
    ll ans=0;
    for(auto e:mp){
        ans+=e.second;
    }
    cout <<ans <<endl;
    return 0;
}

Measured memory_bytes: 4388
#ifdef HIRO
#include "../stdc++.h"
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#include <bits/stdc++.h>
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;


int main() {
#ifdef HIRO
  ifstream cin("input.txt");
  std::cin.rdbuf(cin.rdbuf());
#endif

  int n;
  cin >> n;
  string s[n];
  int t[n];
  for(int i = 0; i < n; i++) {
    cin >> s[i] >> t[i];
  }
  string sle;
  cin >> sle;
  int count = 0;
  bool found = false;
  for(int i = 0; i < n; i++) {
    if(found)
      count += t[i];
    else if(s[i].compare(sle) == 0)
      found = true;
    if(!found && s[i].compare(sle) != 0)
      continue;
  }
  cout << count;
  
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>

int main()
{
    std::string stations;
    std::cin >> stations;
    bool ret = true;

    auto origin = stations[0];
    for(int i = 0; i < stations.length(); i++)
    {
        if(stations[i] != origin)
            ret = false;
    }

    if(!ret)
    {
        std::cout << "Yes";
    } else {
        std::cout << "No";
    }

    return EXIT_SUCCESS;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        int a =  10 * (Integer.valueOf(s[0]) -48)  + Integer.valueOf(s[1]) - 48;
        int b = 10 * (Integer.valueOf(s[2]) -48)  + Integer.valueOf(s[3]) - 48;


        if (a == 0) {
            if (b > 0 &&  b <= 12) {
                System.out.println("YYMM");
            } else {
                System.out.println("NA");
            }
        } else if (a > 0 && a <= 12){
            if (b == 0) {
                System.out.println("MMYY");
            } else if (b > 0 && b <= 12) {
                System.out.println("AMBIGUOUS");
            } else {
                System.out.println("MMYY");
            }
        } else {
            if (b == 0 ) {
                System.out.println("NA");
            } else if (b > 0 && b <= 12) {
                System.out.println("YYMM");
            } else {
                System.out.println("NA");
            }
        }
    }
}

Measured memory_bytes: 22868
#include<bits/stdc++.h>
using namespace std;
long long a[4];
void solve()
{
    sort(a,a+4);
    if (a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9) puts("YES");
    else puts("NO");
}
int main()
{
    while(cin>>a[0]>>a[1]>>a[2]>>a[3])
        solve();
}

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

namespace AC {
#define ll long long
#define PLL pair<ll, ll>
#define PDD pair<double, double>
#define PDPLL pair<double, PLL>
#define PLPLL pair<ll, PLL>
#define pb push_back
#define fi first
#define se second
#define ls rt << 1
#define rs rt << 1 | 1

    const ll N = 1e5 + 66;

    ll BUGS = 1;

    inline ll read(){
        ll x = 0;    bool flag = 1;   char ch = getchar();
        while(ch < '0' || ch > '9') { if(ch == '-') flag = 0; ch = getchar(); }
        while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
        if(flag) return x;  return (~(x - 1));
    }

    inline void read(ll arr[], ll s, ll e) { for(ll i = s; i <= e; ++i) arr[i] = read(); }

    inline void write(ll x){
        if(x < 0) { x = ~(x - 1); putchar('-'); }
        if(x > 9) write(x / 10); putchar(x % 10 + '0');
    }

    inline void print(ll x) { write(x); puts(""); }

    inline void print(ll arr[], ll s, ll e) {
        for(ll i = s; i <= e - 1; ++i) write(arr[i]), putchar(' ');
        write(arr[e]); puts("");
    }

    inline ll max3(ll a, ll b, ll c) { return max(a, max(b, c)); }

    inline ll min3(ll a, ll b, ll c) { return min(a, min(b, c)); }

    inline void debugNum(ll num, string ss) { cout << "BUGS" << BUGS++ << " : " << ss << " : " << num << endl; }

    inline void debugArr(ll arr[], ll s, ll e, string ss) {
        cout << "BUGS" << BUGS++ << " : " << ss << " : " << endl;
        for(ll i = s; i <= e; ++i) cout << "i : " << i << " val : " << arr[i] << endl;
    }

    inline void IO() {
        //ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
        //cout << setiosflags(ios::fixed) << setprecision(1); //保留小数点后1位
        //cout << setprecision(1); //保留1位有效数字
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
}using namespace AC;

ll a, b, c, k;

int main() {
    //IO();
    while(cin >> a >> b >> c >> k) {
        while(k > 0 && b <= a) b *= 2, k--;
        while(k > 0 && c <= b) c *= 2, k--;
        if(c > b && b > a) puts("Yes");
        else puts("No");
    }
    return 0;
}



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

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

  string str;
  cin >> str;

  for(int i = 0; i < str.size() - 8; i++){
    cout << str[i];
  }
  cout << endl;
    
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
typedef long long ll;

int main(){
	ll n;
	cin >> n;
	vector<ll> a(n);
	map<ll,int> mp;
	rep(i,n){
		cin >> a[i];
		mp[a[i]]++;
	}
	sort(a.rbegin(),a.rend());
	ll h = 0;
	ll w = 0;
	rep(i,n){
		if(h == 0 && mp[a[i]] >= 4){
			cout << a[i]*a[i] << endl;
			return 0;
		}
		if(mp[a[i]] >= 2){
			if(h != 0 && h != a[i]){
				w = a[i];
				cout << h * w << endl;
				return 0;
			}
			if(h == 0){
				h = a[i];
			}
		}
	}
	cout << 0 << endl;
	
    return 0;
}



Measured memory_bytes: 7296
// compile in C++11. use -std=c++11.
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

// this require C++11
#include <unordered_set>
#include <unordered_map>
#include <random>

using namespace std;

#define all(c) c.begin(),c.end()
#define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++)
#define debug(x) #x << "=" << (x)
#define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl

typedef complex<double> point;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& vec){
    os << "[";
    for(const auto& v : vec){
        os << v << ",";
    }
    os << "]";
    return os;
}

template<typename T>
T input(){
    T t;cin >> t;
    return t;
}

template<typename T>
vector<T> input(const int N){
    vector<T> v(N);
    repeat(i,N) cin >> v[i];
    return v;
}
const double EPS = 1e-7;
int solve(vector<point> ps){
    int n = ps.size();
    int ret = 1;
    for(int apple=0;apple<n;apple++){
        for(int banana=0;banana<n;banana++){
            if(apple == banana) continue;
            int cur = 0;
            point a = ps[apple];
            point b = ps[banana];
            point vec = a - b;
            point unit_vec = vec / (abs(vec)+EPS);
            point check = b + unit_vec;
            for(const point& p : ps){
                if(abs(check-p) <= 1 + EPS){
                    cur++;
                }
            }
            ret = max(ret,cur);
        }
    }
    return ret;
}

int main(){
    while(true){
        int n = input<int>();
        if(n == 0) break;
        vector<point> ps;
        repeat(apple,n){
            double x,y;
            char c;
            cin >> x >> c >> y;
            ps.push_back(point(x,y));
        }
        cout << solve(ps) << endl;
    }
    return 0;
}

Measured memory_bytes: 1268
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main() {
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    int a = tx - sx, b = ty - sy;
    rep(i, b) cout << "U";
    rep(i, a) cout << "R";
    rep(i, b) cout << "D";
    rep(i, a + 1) cout << "L";
    rep(i, b + 1) cout << "U";
    rep(i, a + 1) cout << "R";
    cout << "DR";
    rep(i, b + 1) cout << "D";
    rep(i, a + 1) cout << "L";
    cout << "U\n";
}

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

string solve(int n) {
  int d = n % 10;
  if(d == 3) {
    return "bon";
  }
  if(d == 0 || d == 1 || d == 6 || d == 8 ) {
    return "pon";
  }
  return "hon";
}

int main() {
  int n;
  cin >> n;
  cout << solve(n);
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(16);

	//cout << setprecision(10) << scientific << ans << endl;
}

signed main() {
	ll n, a, b;

	cin >> n >> a >> b;

	cout << min(n * a, b) << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

// ABC172-B
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		char[] t = sc.next().toCharArray();

		int count = 0;
		for (int i = 0; i < s.length; i++) {
			if (s[i] != t[i]) {
				count++;
			}
		}

		System.out.println(count);
		sc.close();
	}

}


Measured memory_bytes: 42148
#include <iostream>
#include <cmath>
#include<iomanip>
const long double PI=3.14159265358979323846;
const long double pd = 180.0 / PI;
int main(){
  long double a,b,x;
  std::cin >> a >> b >> x;

  long double v = a*a*b;
  long double ans;
  long double h;
  long double r;
  if (x > v/2){
    h = (v - x) / a / a * 2.0;
  	r = atanl(h / a) * pd;
  }
  else {
    h = x / b / a * 2.0;
  	r = 90.0 - atanl(h / b) * pd;
  }

  std::cout <<std::setprecision(10)<< r << std::endl;

  return 0;
}

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;

	map<int, map<int, int>> mp;
	vector<int> p(m), y(m);
	for (int i = 0; i < m; i++) {
		cin >> p[i] >> y[i];
		mp[p[i]][y[i]]++;
	}

	for (auto& imp : mp) {
		int i = 1;
		for (auto& it : imp.second)
			it.second = i++;
	}

	for (int i = 0; i < m; i++)
		printf("%06d%06d\n", p[i], mp[p[i]][y[i]]);
}

Measured memory_bytes: 16384
#Bubble Sort

def printout(array, n):
    output = ""
    for i in range(n - 1):
        output += str(array[i]) + " "
    output += str(array[N - 1])
    print(output)


N = int(input())
array = [int(i) for i in input().split()]
count = 0;
for i in range(N):
    for j in reversed(range(i+1,N)):
        if (array[j-1] > array[j]):
            tmp = array[j]
            array[j] = array[j-1]
            array[j-1] = tmp
            count += 1
printout(array,N)
print(count)


Measured memory_bytes: 5604
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){
    int N, K;
    cin >> N >> K;

    string S;
    cin >> S;

    int cnt = 0;

    int l=-1, r=-1;
    for(int i=0; i<S.length(); i++){
        if(cnt >= K) break;
        if(S[i] != S[i+1] && l == -1) l = i+1;
        else if(S[i] != S[i+1] && r == -1) r = i;

        if(l != -1 && r == -1 && i == S.length()-1) r=i;

        if(l != -1 && r != -1){
            cnt++;
            string t;
            if(S[l] == 'R') t = "L";
            else t = "R";
            for(int j=l; j<=r; j++){
                S.replace(j, 1, t);
            }
            r = l = -1;
        }
    }

    int ans = 0;
    for(int i=0; i<S.length()-1; i++){
        if(S[i] == S[i+1]) ans++;
    }
    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 512
#include <iostream>

using namespace std;
long long n,i,s,d,val, nr;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>val>>nr;
        s+=nr*val;
        d+=nr;
    }
    s-=9;
    if(s<=0)
    {
        s=0;
    }
    else
    {
        if(s%9==0)
            s=s/9;
        else
            s=s/9+1;
    }

    cout<<d-1+ s;
    return 0;
}


Measured memory_bytes: 256
n=int(input())
t=n
g=0
while g==0:
  b=0
  for i in range(n):
    if i!=0 and i!=1:
      a=t%i
      if a==0:
        b=1
  if b==0:
    print(t)
    exit()
  else:
    t+=1


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
int main(){
    int n;
    cin >> n;
    int a,b;
    cin >> a >> b;
    if (n==1){
        cout << "Hello World" << endl;
    }else{
        cout << a+b <<endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#include<cstdio>
#define el "\n"
#define sp " "
typedef long long ll;

main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin>>n;
	vector<ll> a(n);
	for(ll i=0;i<n;i++)
		cin>>a[i];
	sort(a.begin(),a.end());
	ll cnt=1,ans=a[n-1],x=n-2;
	while(cnt!=n-1)
	{
		if(cnt+2<=n-1)
			ans+=2*a[x],cnt+=2;
		else if(cnt+2>n-1)
		{
			ans+=a[x];
			break;
		}
		x--;
	}
	cout<<ans;
	


	


		

	
	
	

	
	
	
	
	
	

	
	
	

}

Measured memory_bytes: 4744
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<unordered_map>
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep2(i,n) for(int i = (n - 1); i >= 0; i--)
#define PI 3.141592653589793

using namespace std;
using ll = long long;

int to[200000];

int main() {

	ll n, k;
	ll ans = -1000000000000000000;
	cin >> n >> k;

	vector<ll> p(n);
	vector<ll> c(n);
	
	rep(i, n)cin >> p[i];
	rep(i, n)cin >> c[i];
	rep(i, n)p[i]--;

	rep(si, n) {
		ll stot = 0;
		ll x = si;
		vector<ll> s;
		while (1) {
			x = p[x];
			s.push_back(c[x]);
			 stot += c[x];
			if (x == si)break;
		}
		ll l = s.size();
		ll tot = 0;
		rep(i, l) {
			tot += s[i];
			if (i + 1 > k)break;
			ll now = tot;
			if (stot>0) {
				ll e = (k - (i + 1)) / l;
				now += stot * e;
			}
			ans = max(ans, now);
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3776
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		int h1 = 0;
		int h2 = 0;
		int h3 = 0;
		Scanner sc = new Scanner(System.in);
		h1 = sc.nextInt();
		h2 = sc.nextInt();
		h3 = sc.nextInt();
		sc.close();
		String strValue = "";
		int diff = h3 - h2;
		if (diff > h1) {
			strValue = "dangerous";
		} else if (diff <= 0) {
			strValue = "delicious";
		} else if (diff <= h1) {
			strValue = "safe";
		}

		System.out.println(strValue);
	}
}

Measured memory_bytes: 22868
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

uint64_t mygcd(uint64_t lhs, uint64_t rhs) {
  if (lhs % rhs == 0) {
    return rhs;
  } else {
    return mygcd(rhs, lhs % rhs);
  }
}

int main() {
  int N, L;
  cin >> N >> L;
  int sum = 0;
  for (int i = 1; i <= N; i++) {
    sum += L + i - 1;
  }
  if (L >= 0) {
    cout << sum - L << endl;
  } else if (L + N - 1 >= 0) {
    cout << sum << endl;
  } else {
    sum -= L + N - 1;
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int L, a, b, c, d;
    int M, N;
    
    scanf("%d\n%d\n%d\n%d\n%d\n",&L, &a, &b, &c, &d);
    M = a/c;
    N = b/d;
    if(a % c != 0)
        M++;
    if(b % d != 0)
        N++;
    if(M > N)
        printf("%d\n", L - M);
    else
        printf("%d\n", L - N);
        
    return 0;
}

Measured memory_bytes: 600
a,b=(int(i) for i in input().split())
#print(a,b)
if a < b:
  if 1 < a:
    print('Bob')
  else:
    print('Alice')
if b < a:
  if 1 < b:
    print('Alice')
  else:
    print('Bob')

if a ==b:
    print('Draw')


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define vi vector<long long int>
#define vs vector<string>
#define mii map<long long int, long long int>

#define inf 1e18+5;


void show(auto a){
  long long int i = 0;
  while(i < a.size()){
    cout<<a[i]<<" ";
    i++;
  }
  cout<<endl;
}




int main(){
  ios_base::sync_with_stdio(false);

  long long int n, W;
  cin>>n>>W;

  vi wt(n), val(n);
  long long int V = 0;
  for(long long int i = 0; i < n; i++) cin>>wt[i]>>val[i], V+=val[i];

  long long int dp[n+1][V+1];

  

  for(long long int j = 0; j <= V; j++)dp[0][j] = inf;
  dp[0][0] = 0;

  for(long long int i = 1; i <= n; i++){
  	for(long long int j = 0; j<=V; j++) dp[i][j] = inf;
  	for(long long int j = 0; j<=V; j++){
  		dp[i][j] = min(dp[i][j], dp[i-1][j]);
  		if(j >= val[i-1]) dp[i][j] = min(dp[i][j], wt[i-1] + dp[i-1][j-val[i-1]]);
  	}
  }
  long long int ans = -1;
  for(long long int i = 0; i <= V; i++){
  	if(dp[n][i] <= W) ans = max(ans, i);
  }


   cout<<ans<<endl;



  
}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const long double pi=acos(-1);
#define x  first
#define y  second
#define read(n,a) for(int i=0;i<n;i++)cin>>a[i];

ll a[100002]={};
//ll b[100002]={};
ll n,m;

int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
    ///freopen("ss.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t=1;
    //cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        ll ans=0;
        for(int i=0;i<s.size();i++)ans+=s[i]-'0';
        if(ans%9==0)cout<<"Yes";
        else cout<<"No";
    }
    return 0;
}


Measured memory_bytes: 3764
# バブルソート
def bubbleSort(list, n):
    cnt = 0  # 要素の交換回数
    for i in range(n-1):
        for j in reversed(range(i+1, n)):
            if list[j] < list[j-1]:
                list[j], list[j-1] = list[j-1], list[j]
                cnt += 1
    return cnt

N = int(input())
array = list(map(int, input().split()))
ans = bubbleSort(array, N)

print(array[0], end="")
for i in range(1, N):
    print(" %d" % array[i], end="")
print("\n%d" % ans)


Measured memory_bytes: 5608
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <sstream>

#define DEBUG 0
#define fi first
#define se second
#define pb push_back
#define INF 1000000000
#define fore(i,a,b) for (int i = (a), _b = (b); i < (_b); ++i)
#define fort(i,a,b) for (int i = (a), _b = (b); i <= (_b); ++i)
#define ford(i,a,b) for (int i = (a), _b = (b); i >= (_b); --i)

using namespace std;

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
    if (DEBUG) {
        freopen("CP.inp", "r", stdin);
        //freopen("CP.out", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    map<string, LL> m;
    while (n--) {
        string s; cin >> s;
        sort(s.begin(), s.end());
        ++m[s];
    }
    LL res = 0;
    for (auto &x : m) {
        res += x.se * (x.se - 1) / 2;
    }
    cout << res << '\n';
    return 0;
}


Measured memory_bytes: 11264
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits>
#include <cmath>

using namespace std;

int main() {
    size_t n;
    cin >> n;
    vector<size_t> a(n, 0);
    for (size_t i = 0; i < n; ++i)
        cin >> a[i];
    for (auto e : a) {
        if (e % 2 == 0) {
            if (e % 3 != 0 && e % 5 != 0) {
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2'009;

int a[2 * N];
int b[2 * N];
int pos[N][2];
int cnt[2 * N][N][2];
int f[N][N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < 2 * n; ++i) {
    char t[5];
    scanf("%s %d", t, a + i);
    b[i] = t[0] == 'W';
  }
  memset(cnt, 0, sizeof cnt);
  for (int i = 0; i < 2 * n; ++i) {
    pos[a[i]][b[i]] = i;
    for (int j = 0; j < i; ++j) {
      cnt[i][a[j]][b[j]] = 1;
    }
    for (int j = n - 1; j >= 0; --j) {
      cnt[i][j][0] += cnt[i][j + 1][0];
      cnt[i][j][1] += cnt[i][j + 1][1];
    }
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      f[i][j] = 1'000'000'000;
    }
  }
  f[0][0] = 0;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (i + 1 <= n) {
        f[i + 1][j] = min(f[i + 1][j], f[i][j] + cnt[pos[i + 1][0]][i + 1][0] + cnt[pos[i + 1][0]][j + 1][1]);
      }
      if (j + 1 <= n) {
        f[i][j + 1] = min(f[i][j + 1], f[i][j] + cnt[pos[j + 1][1]][j + 1][1] + cnt[pos[j + 1][1]][i + 1][0]);
      }
    }
  }
  printf("%d\n", f[n][n]);
}


Measured memory_bytes: 78976
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    mod=10**9+7
    ans=0
    s=0
    n=int(input())
    a = [int(x) for x in input().split()]
    for x in a:
        ans+=s*x
        ans%=mod
        s+=x
        s%=mod
    print(ans)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

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

ll N, M;

/*
   dp1[i][j] : S[0..i]とT[0..j] の部分列が一致し、かつS[i]とT[j]を使用する組み合わせの数 
   dp1[-1][-1] = 1 : 部分列が()の場合を表す
   
   acc[i][j] : dp1[-1..i][-1..j]の合計
   
*/
ll dp1[2001][2001];
ll acc[2001][2001];
const ll MOD = 1000000007;

int main(){
	cin >> N >> M;
	
	vector<ll> S(N);
	vector<ll> T(M);
	for ( int i = 0; i < N; i++ )
		cin >> S[i];
	for ( int i = 0; i < M; i++ )
		cin >> T[i];
	
	for ( int i = 0; i < N; i++ ){
		for ( int j = 0; j < M; j++ ){
			dp1[i][j] = 0;
			acc[i][j] = 0;
		}
	}
	
	for ( int i = 0; i < N; i++ ){
		ll asum = 0;
		for ( int j = 0; j < M; j++ ){
			if ( S[i] == T[j] ){
				dp1[i][j] = (i-1<0||j-1<0) ? 1 : acc[i-1][j-1];
			}
			asum = (asum + dp1[i][j])%MOD;
			acc[i][j] = (((i-1<0)?1:acc[i-1][j]) + asum)%MOD;
		}
	}
	
//	for ( int i = 0; i < N; i++ ){
//		for ( int j = 0; j < M; j++ ){
//			cout << dp1[i][j] << " ";
//		}
//		cout << endl;
//	}
//	cout << endl;
//	
//	for ( int i = 0; i < N; i++ ){
//		for ( int j = 0; j < M; j++ ){
//			cout << acc[i][j] << " ";
//		}
//		cout << endl;
//	}
//	cout << endl;
	
	
	cout << acc[N-1][M-1] << endl;
	
	return 0;
}



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

int main() {
  int A, B, C, K, ans = 0;
  cin >> A >> B >> C >> K;

  while (K--) {
    if (A) {
      A--;
      ans++;
    } else if (B) {
      B--;
    } else if (C) {
      C--;
      ans--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
sx, sy, tx, ty = map(int, input().split())
x_plus = tx - sx
y_plus = ty - sy
first_go = 'R'*x_plus + 'U'*y_plus
first_back = 'L'*x_plus + 'D'*y_plus
second_go = 'DR' + first_go + 'UL'
second_back = 'UL' + first_back + 'DR'
print(first_go + first_back + second_go + second_back)

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

hoge = []
for a in A:
    if a % 2 == 0:
        hoge.append(a)

count = 0
for h in hoge:
    if h % 3 == 0 or h % 5 == 0:
        count = count + 1

if len(hoge) == count:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 38384
#include<stdio.h>
int flg[999999];
int main(void)
{
	int a,i,j,X,x,s;
	while((scanf("%d",&a))!=EOF){
		for(i=2;i<=a;i++){
			flg[i]=0;
		}
		for(i=2;i<=a;i++){
			X=i;
			x=0;
			x=a/i;
			for(j=0;j<x-1;j++){
				X+=i;
				flg[X]=1;
			}
		}
		s=0;
		for(i=2;i<=a;i++){
			if(flg[i]==0){
				s++;
			}
		}
		printf("%d\n",s);
	}
	return 0;
}

Measured memory_bytes: 4496
#include<bits/stdc++.h>
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define pb push_back
#define N 900000
#define ar array
typedef long long int ll;
using namespace std;
int main(void){
	fast;
	//cout<<"**"<<endl;
	ll ans=0,n,i,j;
	cin>>n;
	for(i=2;i<=n;i++){
		for(j=i;j<=n;j+=i)
		ans+=j;
	}
	ll a1=n*(n+1)/2;
	ans+=a1;
	cout<<ans<<endl;
}


Measured memory_bytes: 3600