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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define LLi long long int

using namespace std;

int imax=2147483647;
long long int llimax=9223372036854775807;

//int型vectorを出力
void PV(vector<int> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

//LLi型vectorを出力
void PVL(vector<LLi> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

int main(){

	int n, x, y, ma=-1;
	vector<int> v1, v2, v3, v4;

	cin>> n;
	v1.resize(n);
	v2.resize(n);
	v3.resize(n);
	v4.resize(n);

	rep(i, n){
		cin >> x >> y;
		v1[i]=x;
		v2[i]=y;
		v3[i]=x+y;
		v4[i]=x-y;
	}
	
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	sort(v3.begin(), v3.end());
	sort(v4.begin(), v4.end());

	ma=max(ma, v1[n-1]-v1[0]);
	ma=max(ma, v2[n-1]-v2[0]);
	ma=max(ma, v3[n-1]-v3[0]);
	ma=max(ma, v4[n-1]-v4[0]);

	cout<< ma << endl;
 
	return 0;
}


Measured memory_bytes: 6424
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
const MOD = int(1e+9) + 7
const INF = 1 << 60

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	H, N := sc.nextInt(), sc.nextInt()
	A := make([]int, N)
	B := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = sc.nextInt()
		B[i] = sc.nextInt()
	}
	dp := make([]int, H+1)
	for i := 0; i <= H; i++ {
		dp[i] = INF
	}
	dp[0] = 0
	for i := 1; i <= H; i++ {
		for j := 0; j < N; j++ {
			ind := j
			if i < A[j] {
				ind = 0
			} else {
				ind = i - A[j]
			}
			dp[i] = min(dp[i], dp[ind]+B[j])
		}
	}

	fmt.Fprintln(wtr, dp[H])
	wtr.Flush()
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,m,i,ans = 0;scanf("%lld%lld",&n,&m);
  pair<long long,long long> d[n];
  for(i=0;i<n;i++) scanf("%lld%lld",&d[i].first,&d[i].second);
  sort(d,d+n);
  for(i=0;i<n;i++){
    if(d[i].second>=m){
      ans += d[i].first*m;break;
    } else {
      ans += d[i].first*d[i].second;m -= d[i].second;
    }
  }
  printf("%lld\n",ans);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
int main(){
    int64_t n;
    cin>>n;
    int64_t ans=1;
    for(int64_t i=1;i<=sqrt(n)+1;i++){
        int64_t c = i*i;
        if(c>ans && n>=c){
            ans = c;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll INF=1e18;
const int MOD=1e9+7;
const double pi=acos(-1);
typedef long long ll;
 
// グラフ
using Edge = pair<int,int>; // {辺の行き先, 重み}
using Graph = vector<vector<Edge>>; // グラフ

Graph G;
vector<int>ans;

void dfs(int v,int p,int c){
  ans[v]=c;
  for(auto e:G[v]){
    if(e.first==p)continue;
    if(e.second&1)dfs(e.first,v,1-c);
    else dfs(e.first,v,c);
  }
}
  
int main(){
  int n;
  cin >> n;
  G.assign(n,vector<Edge>());
  rep(i,n-1){
    int u,v;
    int w;
    cin >> u >> v >> w;
    u--;
    v--;
    G[u].push_back(Edge(v,w));
    G[v].push_back(Edge(u,w));
  }
  ans.assign(n,0);
  dfs(0,-1,1);
  for(auto v:ans)cout<<v << endl;
}


Measured memory_bytes: 8960
#include<stdio.h>

int main(void){

int a=0;
int b=0;
int k=0;

scanf("%d",&a);
scanf("%d",&b);

if(a%2!=b%2){
  printf("IMPOSSIBLE");
}else{
  k=(a+b)/2;
  printf("%d",k);
}
return 0;
}


Measured memory_bytes: 128
import java.util.*;
public class Main {

    public static void main(String[] args) {
        //data input
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        long ct = 0;

        for (int i = 1; i < n; i++) {
            int m = n - i;
            if (m <= i) break;
            if (m + i == n) ct++;
        }

        System.out.println(ct);
    }
}

Measured memory_bytes: 23764
def main():
    N, M = map(int, input().split())
    A = [int(x) for x in input().split()]
    BC = [list(map(int, input().split())) for i in range(M)]

    BC.sort(key=lambda x: x[1], reverse=True)
    A.sort()
    index = 0
    for j in range(M):
        if index >= N:
            break
        elif A[index] > BC[j][1]:
            break
        for i in range(BC[j][0]):
            if index >= N:
                break
            elif A[index] < BC[j][1]:
                A[index] = BC[j][1]
                index += 1

    print(sum(A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 81688
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
int n, nn, q;
long long a[100005], ans[100005], num[100005];
stack<long long> s;
void solve(long long len, long long sum)
{
    int pos = lower_bound(a + 1, a + nn + 1, len) - a - 1;
    if (!pos)
    {
        ans[1] += sum;
        ans[len + 1] -= sum;
        return;
    }
    num[pos] += len / a[pos] * sum;
    solve(len % a[pos], sum);
}
int main(int argc, char const *argv[])
{
    scanf("%d%d", &n, &q);
    s.push(n);
    for (int i = 1; i <= q; i++)
    {
        long long x;
        scanf("%lld", &x);
        while (!s.empty() && x < s.top())
        {
            s.pop();
        }
        s.push(x);
    }
    nn = s.size();
    for (int i = nn; i >= 1; i--)
    {
        a[i] = s.top();
        s.pop();
    }
    num[nn] = 1;
    for (int i = nn; i >= 1; i--)
    {
        solve(a[i], num[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        ans[i] += ans[i - 1];
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

Measured memory_bytes: 6892
M, D = map(int, input().split())

ans = 0
for m in range(1, M+1):
    for d in range(10, D+1):
        d1 = int(str(d)[0])
        d10 = int(str(d)[1])
        if d1 >= 2 and d10 >= 2 and d1*d10 == m:
            ans += 1
print(ans)


Measured memory_bytes: 2940
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

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

#define MOD 1000000007

void solve(int test_case) {//227
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(abs(a-c)<=d||(abs(a-b)<=d&&abs(b-c)<=d))cout<<"Yes";
	else cout<<"No";
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3640
S = input()

Y = False
M = False
if 1 <= int(S[:2]) <= 12:
    Y = True
if 1 <= int(S[2:]) <= 12:
    M = True

if Y and M:
    print("AMBIGUOUS")
elif Y and not M:
    print("MMYY")
elif not Y and M:
    print("YYMM")
else:
    print("NA")


Measured memory_bytes: 2940
#include<stdio.h>
bool table[500][500];
int f[500];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)table[i][j]=false;
		for(int i=0;i<a;i++)f[i]=0;
		for(int i=0;i<b;i++){
			int c,d;
			scanf("%d%d",&c,&d);
			table[c-1][d-1]=true;
			table[d-1][c-1]=true;
		}
		for(int i=1;i<a;i++){
			if(table[0][i])f[i]=1;
		//	printf("%d ",f[i]);
		}
		for(int i=0;i<a;i++){
			if(f[i]==1){
				for(int j=0;j<a;j++)if(table[i][j]&&f[j]==0)f[j]=2;
			}
		}
		int ret=0;
		for(int i=0;i<a;i++)if(f[i])ret++;
		if(ret>0)printf("%d\n",ret-1);
		else printf("0\n");
	}
}

Measured memory_bytes: 0
/* 
   AOJ 1285 
   Grey Area
   
*/

#include<stdio.h>
#include<stdlib.h>

#define N_MAX 100
#define BAR_MAX 11

struct fraction
{
  int numerator, denominator;
};

struct fraction mul(struct fraction x, struct fraction y)
{
  struct fraction z;
  z.numerator = x.numerator * y.numerator;
  z.denominator = x.denominator * y.denominator;
  return z;
}

int main(void)
{
  int i, val_n, width, v, max = -1, max_bar, bar_max = -1, rightest_bar, nume_sum = 0;
  int datasets[N_MAX] = {0};
  int bars[BAR_MAX] = {0};
  double nume, denom;
  struct fraction fraction_bars[BAR_MAX];
  struct fraction ink_percentage;
  while(1)
    {
      for(i = 0; i < BAR_MAX; i++)
	{
	  bars[i] = 0;
	}

      scanf("%d %d", &val_n, &width);
      if(val_n == 0 && width == 0)
	{
	  break;
	}
      for(i = 0; i < val_n; i++)
	{
	  scanf("%d", &datasets[i]);
	}
      
      /* sort(datasets, 0, val_n - 1); */
      /* qsort(datasets, val_n, sizeof(int), comp); */
      
      for(i = 0; i < val_n; i++)
	{
	  if(max < datasets[i])
	    {
	      max = datasets[i];
	    }
	  v = datasets[i] / width;
	  bars[v]++;
	}
      
      rightest_bar = max / width;

      for(i = 0; i < BAR_MAX; i++)
	{
	  if(bar_max < bars[i])
	    {
	      bar_max = bars[i];
	      max_bar = i;
	    }
	  /* printf("%4d", bars[i]); */
	}

      /* printf("\n%d %d\n", rightest_bar, max_bar); */
      


      for(i = 0; i <= rightest_bar; i++)
	{
	  fraction_bars[i].numerator = bars[i];
	  fraction_bars[i].denominator = bars[max_bar];

	  ink_percentage.numerator = rightest_bar - i;
	  ink_percentage.denominator = rightest_bar;

	  fraction_bars[i] = mul(fraction_bars[i], ink_percentage);
	  /* printf("%d/%d ", fraction_bars[i].numerator, fraction_bars[i].denominator); */

	  nume_sum += fraction_bars[i].numerator;
	}
      nume = (double)nume_sum;
      denom = (double)fraction_bars[0].denominator;
      printf("%lf\n", nume / denom + 0.01);
      bar_max = -1;
      max = -1;
      nume_sum = 0;
    }
  
  return 0;
}

Measured memory_bytes: 636
#include <iostream>
#define ll long long

using namespace std;

int countRainy(string s)
{
    int count = 0;
    int localCount = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'R')
        {
            localCount++;
        }
        else
        {
            if (localCount > count)
                count = localCount;
            localCount = 0;
        }
    }
    if (localCount > count)
        count = localCount;
    return count;
}

int main()
{
    string s;
    cin >> s;
    cout << countRainy(s) << endl;
}

Measured memory_bytes: 3172
t= [list(map(int, input().split())) for _ in range(3)]
for i in range(3):
    r= t[i]
    if r[5]-r[2]>= 0:
        s= r[5]-r[2]
    else:
        s= 60-(r[2]-r[5])
        r[4]-= 1
    if r[4]-r[1]>= 0:
        m= r[4]-r[1]
    else:
        m= 60-(r[1]-r[4])
        r[3]-= 1
    h= r[3]-r[0]
    print(h, m, s)

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

int main(){
    int n;
    string s;
    cin >> n;
    cin >> s;
    int char_count[26];
    for(int i=0; i<26; i++){
        char_count[i] = 0;
    }

    for(int i=0; i<n; i++){
        char_count[s[i] - 'a'] ++ ;
    }

    long long int plus, notplus, total, temp1, temp2;
    plus = char_count[0];
    notplus = 0;
    total = plus;
    for(int i=1; i<26; i++){
        temp1 = plus;
        temp2 = notplus;
        plus = ((plus + notplus + 1) * char_count[i])% (int)(1e9 + 7);
        notplus = (temp1 + temp2)% (int)(1e9 + 7);
        total += plus;
        total = total % (int)(1e9 + 7);
    }

    
    cout << total << endl;
    return 0;
}

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

using namespace std;

#define ll long long
#define MOD 1000000007

int main()
{
	ll n, m;
	cin >> n >> m;

	vector < ll > x(n), y(m);

	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> y[i];
	}

	ll a = 0, b = 0;

	for (ll i = 0; i < n; i++) {
		a = (a + (2 * (i + 1) - 1 - n) * x[i] % MOD) % MOD;
	}

	for (ll i = 0; i < m; i++) {
		b = (b + (2 * (i + 1) - 1 - m) * y[i] % MOD) % MOD;
	}

	ll ans = a * b % MOD;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1792
n = int(input())

a = "abcdefghijklmnopqrstuvwxyz"
s = ""

while n > 0:
    if n%26 == 0:
        s = a[n%26-1] + s
        n //= 26
        n -= 1
    else:
        s = a[n%26-1] + s
        n //= 26
    
print(s)

Measured memory_bytes: 8840
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(a) (a).begin(), (a).end()
typedef vector<int> vi;
const int INF = 1LL << 60; //10e18+10e17ちょっとくらい
const int MOD = 1000000007;
const int MAX_N = 200100;

signed main()
{
    //  以降 cin の入力元が 'input.txt' になる
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;

    return 0;
}

Measured memory_bytes: 3652
#!/usr/bin/env python3
#ABC130 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

w,h,x,y = LI()
ans = [0,0]
if w/2 == x and h/2 == y:
    ans[1] = 1
ans[0] = (w*h)/2
print(*ans)


Measured memory_bytes: 38384
dp=[0]*4001
for i in range(4001):
    if i<1000:
        dp[i]=i+1
    elif i>2000:
        dp[i]=0
    elif i>=1000:
        dp[i]=2001-i
while 1:
    try:
        ans=0
        n=int(input())
        for i in range(n+1):
            ans+=dp[i]*dp[n-i]
        print(ans)
    except:break


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

int main() {
  int h, w;
  cin >> h >> w;
  
  char table[55][55];
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> table[i][j];
    }
  }

  int count = 0;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      // == '.'だと何も入ってないマスを正しく処理できない
      if (table[i][j] == '#' and table[i-1][j] != '#' and table[i][j+1] != '#' and table[i+1][j] != '#' and table[i][j-1] != '#') count++;
    }
  }
  
  cout << (count ? "No" : "Yes") << endl;
}


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

int main(){
    string s;
    cin >> s;

    int ans = 0;
    rep(i, s.size()/2){
        // cout << i << ' ' << s.at(i) << s.at(s.size()-i-1) << endl;

        if(s.at(i)!=s.at(s.size()-i-1)){
            ans +=1;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import random

def is_prime3(q, k=50):
    q = abs(q)
    #?¨???????????????§?????????????????§????????????????????????
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*d??¨????????????a?????´??°???d????\???°)???d????±???????
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #?????????k?????°?????????
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]??????????????????????????§??????
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

if __name__=="__main__":
    n = int(input())
    a = []
    for i in range(n):
        a.append(int(input()))
    b = []
    for i in range(n):
        b.append(is_prime3(a[i]))
    print(b.count(True))

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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;

int main()
{
  int A, B;
  cin >> A >> B;
  if (A >= 13)
    cout << B << endl;
  else if (A <= 12 and A >= 6)
    cout << B / 2 << endl;
  else
    cout << 0 << endl;
}


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

using namespace std;

int main(void) {
  int n, k;
  while (cin >> n >> k, n) {
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }

    set<string> st;
    for (int i = 0; i < 1 << n; i++) {
      if (bitset<10>(i).count() != k) continue;
      vector<int> b;
      for (int j = 0; j < n; j++) {
        if (i >> j & 1) {
          b.push_back(j);
        }
      }

      do {
        string w = "";
        for (int j = 0; j < k; j++) {
          w += a[b[j]];
        }
        st.insert(w);
      } while (next_permutation(b.begin(), b.end()));
    }

    cout << st.size() << endl;
  }

  return 0;
}


Measured memory_bytes: 3404
#include <bits/stdc++.h>
#define Mashu cout << "UUZ ate it." << endl
#define RE register int
#define ll long long
using namespace std;

inline int read(){
	char ch=getchar();
	int x=0,cf=1;
	while(ch<'0'||ch>'9') {
		if(ch=='-') cf=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*cf;
}

int G[55];
template<class T> inline void write(T x){
	int g=0;
	do{G[++g]=x%10;x/=10;}while(x);
	for(int i=g;i>=1;--i)putchar('0'+G[i]);putchar('\n');
}

char a[200010];

int main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int W = 0, R = 0;
	for (int i = 1; i <= n; i++){
		if (a[i] == 'R') R++;
		else W++;
	}
	int cnt = 0, cnt2 = 0;
	for (int i = R + 1; i <= n; i++){
		if (a[i] == 'R') cnt++;
	}
	for (int i = n - W; i >= 1; i--){
		if (a[i] == 'W') cnt2++;
	}
	cout << min(cnt, cnt2) << endl;
	return 0;
	Mashu;
}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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 (a>b) { a=b; return 1; } return 0; }



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ld n, m, d;
  cin >> n >> m >> d;

  ld ans = (n - d) * 2 * (m - 1) / n / n;
  if (d == 0) ans /= 2;
  cout << ans << '\n';


  

  
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main() {
int s;
scanf("%d", &s);
 
int h = s / 3600;
s %= 3600;
 
int m = s / 60;
s %= 60;
 
printf("%d:%d:%d\n", h, m, s);
 
return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<int, int>;
using PL = pair<lint, lint>;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr lint B1 = 1532834020;
constexpr lint M1 = 2147482409;
constexpr lint B2 = 1388622299;
constexpr lint M2 = 2147478017;
constexpr int INF = 2147483647;
void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";}
template<class T>void chmax(T &a, const T &b) { if (a<b) a=b; }
template<class T>void chmin(T &a, const T &b) { if (b<a) a=b; }
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  lint N;
  cin >> N;
  lint ans = 0;
  FOR(A, 1, N) {
    ans += (N-1) / A;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3648
#include <cstdio>
#include <algorithm>

#define N 100
int main(){
    int n;
    std::scanf("%d", &n);

    int p[N+1];
    int m[N+1][N+1];

    for(int i = 1; i <= n; ++i){
        std::scanf("%d", &p[i - 1]);
        std::scanf("%d", &p[i]);
        m[i][i] = 0;
    }

    for(int l = 2; l <= n; ++l){
        for(int i = 1; i <= n - l + 1; ++i){
            int j = i + l - 1;
            m[i][j] = 0x7FFFFFFF;//large value;                                                                                                                                                                                     
            for(int k = i; k <= j -1; ++k){
                m[i][j] = std::min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
            }
        }
    }
    std::printf("%d\n", m[1][n]);

    return 0;
}



Measured memory_bytes: 2764
#include <bits/stdc++.h>
using namespace std;
int main(){
  int P,Q,R;
  cin >> P >> Q >> R;
  int A=P+Q, B=Q+R, C=P+R;
  if (A > B) {
    if (B < C) {
      cout<< B <<endl;
    }
    else {
      cout<< C <<endl;
    }
  }
  else {
    if (A < C) {
      cout<<A <<endl;
    }
    else {
      cout<< C <<endl;
    }
  }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		int[]A = new int[N];
		long sum = 0;
		for(var i=0;i<N;i++){
			A[i] = int.Parse(Console.ReadLine());
			sum += A[i];
		}
		Array.Sort(A);
		long[,]D = new long[N,sum+1];
		long mod = 998244353;
		D[0,A[0]] = 1;
		D[0,0] = 2;
		for(var i=1;i<N;i++){
			for(var j=0;j<=sum;j++){
				if(j+A[i]<=sum){
					D[i,j+A[i]] = (D[i,j+A[i]]+D[i-1,j]) % mod;
				}
				D[i,j] = (D[i,j]+D[i-1,j]*2) % mod;
			}
		}
		long ans = 1;
		for(var i=0;i<N;i++){
			ans = ans * 3 % mod;
		}
		for(var i=(sum+1)/2;i<=sum;i++){
			ans = ans + mod * 3 - D[N-1,i] * 3;
			ans %= mod;
		}
		ans %= mod;
		long[,]D2 = new long[N,sum+1];
		D2[0,A[0]] = 1;
		D2[0,0] = 1;
		for(var i=1;i<N;i++){
			for(var j=0;j<=sum;j++){
				if((j+A[i])*2<=sum){
					D2[i,j+A[i]] = (D2[i,j+A[i]]+D2[i-1,j]) % mod;
				}
				D2[i,j] = (D2[i,j]+D2[i-1,j]) % mod;
			}
		}
		if(sum%2==0){
			ans += D2[N-1,sum/2] * 3;
		}
		ans %= mod;
		Console.WriteLine(ans);
	}
}

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

using namespace std;

#define int long long
#define INF 1e9
#define LINF 1e18

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int H, N;
int no_put[10000];
int dp[2][1 << 4];

int pat[] = {0b0000, 0b0011, 0b0110, 0b1100, 0b1111};
int score[] = {0, 1, 1, 1, 2};

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

    cin >> H >> N;
    for(int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        no_put[y] |= 1 << x;
    }
    int *front = dp[0];
    int *back = dp[1];
    for(int i = 0; i < (1 << 4); ++i) {
        if(i & no_put[0]) front[i] = -1;
        else front[i] = 0;
    }
    int res = 0;
    for(int i = 0; i < H - 1; ++i) {
        fill(back, back + (1 << 4), -1);
        for(int j = 0; j < (1 << 4); ++j) {
            if(front[j] == -1) continue;
            for(int k = 0; k < 5; ++k) {
                int flag1 = pat[k] & no_put[i];
                int flag2 = pat[k] & no_put[i + 1];
                if(!flag1 && !flag2 && !(j & pat[k])) {
                    int next = pat[k] | no_put[i + 1];
                    chmax(back[next], front[j] + score[k]);
                }
            }
        }
        for(int j = 0; j < (1 << 4); ++j) chmax(res, back[j]);
        int *tmp = front;
        front = back;
        back = tmp;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3228
#include <stdio.h>

#define N 100

int main()
{
  int i,j,minj,k,d=0,n,A[N];

  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&A[i]);

  for(i=0;i<n;i++){
    minj = i;
    for(j=i;j<n;j++){
      if(A[j] < A[minj]){
	minj = j;
      }
    }
     if(A[minj] != A[i]){
	k = A[i];
	A[i] = A[minj];
	A[minj] = k;
	d++;
      }
  }

  for(i=0;i<n-1;i++) printf("%d ",A[i]);
  printf("%d\n",A[n-1]);
  printf("%d\n",d);

  return 0;
}
  



Measured memory_bytes: 2044
//---------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#include<algorithm>
//---------------------------------------------------------------
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define SIZE 100005
#define INF 1000000000000000LL
#define all(x) x.begin(),x.end()
#define fi first
#define se second
using pint = pair<int,int>;
using vec = vector<int>;
using ll=long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
//---------------------------------------------------------------
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
//---------------------------------------------------------------

//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓


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

    ll n;cin>>n;
    vll h(n);
    rep(i,n) cin>>h[i];
    
    rep(i,n-1){
        if(h[i] > h[i+1]){
            cout<<"No"<<endl;
            return 0;
        }else{
            if(h[i]!=h[i+1])h[i+1]--;
        }
    }

    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 3952
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define rrep(i,n) for(int (i)=1;i<=(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define INF 1e18
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};

struct edge {
	int to, index;
};

vector<vector<edge>> graph;
vector<int> ret;

void dfs(int v, int preColor) {
	int color = 1;
	for(auto nextEdge : graph[v]) {
		if(ret[nextEdge.index] == 0) {
			if(color == preColor) color++;
			ret[nextEdge.index] = color;
			dfs(nextEdge.to, color);
			color++;
		}
	}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	
	int n;
	cin >> n;
	graph = vector<vector<edge>>(n);
	vector<int> count(n);
	rep(i, n-1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		edge x, y;
		x.to = b, x.index = i;
		y.to = a, y.index = i;
		graph[a].push_back(x);
		graph[b].push_back(y);
		count[a]++, count[b]++;
	}

	int maxCount = 0, maxIndex = -1;
	rep(i, n) {
		if(maxCount < count[i]) {
			maxCount = count[i];
			maxIndex = i;
		}
	}
	cout << maxCount << endl;
	ret = vector<int>(n-1);
	dfs(maxIndex, 0);
	for(auto x : ret) cout << x << endl;
	return 0;
}

Measured memory_bytes: 12092
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
typedef long long ll;
const int INF = 1<<29;
const int N = 1e6 + 9;
ll a[N];
bool cmp(const pair<double, ll> &a, const pair<double, ll> &b)
{
    if(a.first == b.first){
        return a.second < b.second;
    }
    return a.second > b.second;
}
int main()
{
    fio;
    ll n;
    cin >> n;
    ll k = (n * (n + 1)) / 2;
    cout << k;
    return 0;
}


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

ll N;
ll A;
ll B;
ll ret1, ret2;

void input(){
    cin >> N >> A >> B;
}
void solve(){
    ret1 = (A>B)?B:A;
    ret2 = A + B - N;
    if(ret2<0) ret2 = 0;
}

int main(void){
    input();
    solve();
    cout << ret1 << " " << ret2<< endl;
}


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

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> Pair;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;

ll N;
VL A;

int main() {
    cin >> N;
    A.resize(N);
    VECCIN(A);
    ll M = *max_element(All(A));
    ll m = *min_element(All(A));
    if(M == m) {
        if(M == N - 1 || 2 * M <= N) {
            cout << "Yes"
                 << "\n";
        } else {
            cout << "No"
                 << "\n";
        }
        return 0;
    } else if(M == m + 1) {
        ll x = 0;
        REP(i, N) {
            if(A[i] == m) {
                x++;
            }
        }
        ll y = N - x;
        if(x < M && 2 * (M - x) <= y) {
            cout << "Yes"
                 << "\n";
        } else {
            cout << "No"
                 << "\n";
        }
        return 0;
    } else {
        cout << "No"
             << "\n";
        return 0;
    }
}


Measured memory_bytes: 1024
import sys

input = sys.stdin.readline


def main():
    K = int(input())

    L = []
    n1 = [[i + 1] for i in range(9)]
    L.append(n1)
    cnt = 0
    if 1 <= K <= 9:
        print(K)
        exit()
    else:
        cnt += 9

    # 10 ~ 99
    n2 = [[] for _ in range(9)]
    L.append(n2)
    for i in range(9):
        base = 11 * (i + 1)
        if i != 8:
            L[1][i].extend([base - 1, base, base + 1])
        else:
            L[1][i].extend([base - 1, base])
        if K <= cnt + len(L[1][i]):
            print(L[1][i][K - cnt - 1])
            exit()
        else:
            cnt += len(L[1][i])

    k = 2
    while True:
        n = [[] for _ in range(9)]
        L.append(n)
        for i in range(9):
            base = (10 ** k) * (i + 1)
            if i == 0:
                ll = []
                ll += [base, base + 1]
                if k >= 3:
                    for m in range(2, k):
                        ll += [base + j for j in L[m-1][0]]
                ll += [base + j for j in L[k-1][i]]
                ll += [base + j for j in L[k-1][i + 1]]
                L[k][i].extend(ll)
            elif i < 8:
                ll = []
                ll += [base + j for j in L[k-1][i - 1]]
                ll += [base + j for j in L[k-1][i]]
                ll += [base + j for j in L[k-1][i + 1]]
                L[k][i].extend(ll)
            else:
                ll = []
                ll += [base + j for j in L[k-1][i - 1]]
                ll += [base + j for j in L[k-1][i]]
                L[k][i].extend(ll)
            if K <= cnt + len(L[k][i]):
                print(L[k][i][K - cnt - 1])
                exit()
            else:
                cnt += len(L[k][i])
        k += 1


if __name__ == "__main__":
    main()


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

int P,Q,R;

int formula(string& f, int& i) {
  switch(f[i++]) {
  case '-' : return 2 - formula(f, i);
  case 'P' : return P;
  case 'Q' : return Q;
  case 'R' : return R;
  case '0' : return 0;
  case '1' : return 1;
  case '2' : return 2;
  case '(' :
    int f1 = formula(f, i);
    int f2;
    switch(f[i++]) {
    case '*' :
      f2 = formula(f, i);
      i++;
      return min(f1, f2);
    case '+' :
      f2 = formula(f, i);
      i++;
      return max(f1, f2);
    }
  }
  
  return 0;
} 

int main() {
  string f;
  while(cin >> f, f[0] != '.') {
    int cnt = 0;
    for (P = 0; P <= 2; P++) {
      for (Q = 0; Q <= 2; Q++) {
	for (R = 0; R <= 2; R++) {
	  int i = 0;
	  if(formula(f, i) == 2) cnt++;
	}
      }
    }
    cout << cnt << endl;
  }
  return 0;
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

int n;
string s;

map<pair<string, string>, ll> mp;

string a, b;
void rec1(int i = 0) {
  if (i == n) {
    mp[{a, b}]++;
    return;
  }
  a.push_back(s[i]);
  rec1(i + 1);
  a.pop_back();
  b.push_back(s[i]);
  rec1(i + 1);
  b.pop_back();
}

ll res = 0;
void rec2(int i = 2 * n) {
  if (i == n) {
    res += mp[{a, b}];
    return;
  }
  a.push_back(s[i - 1]);
  rec2(i - 1);
  a.pop_back();
  b.push_back(s[i - 1]);
  rec2(i - 1);
  b.pop_back();
}

signed main() {
#ifdef LOCAL
  assert(freopen("c.in", "r", stdin));
#endif
  cin >> n >> s;
  rec1();
  rec2();
  cout << res << '\n';
}


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

long long solve(long long curr, int N, int K)
{
    if(N == 0)
        return curr;
    
    return min(solve(curr + K, N-1, K), solve(curr * 2, N-1, K));
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);

    long long N, K;
    cin >> N >> K;

    cout << solve(1, N, K) << "\n";
    return 0;
}


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

using i64 = int64_t;

int main(){
    string s;
    cin >> s;
    int k;
    cin >> k;
    set<string> st;
    for(int i=1;i<=5;++i){
        for(int j=0;j<s.size();++j){
            if(j+i > s.size())break;
            st.insert(s.substr(j, i));
        }
    }

    auto ans = st.begin();
    for(int i=1;i<k;++i)ans++;
    cout << *ans << endl;

    return 0;
}

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

using namespace std;

int n;
char a[4010];
long long ssum;
long long R, G, B;

int main(void)
{
	scanf("%d", &n);
	scanf("%s", a);
	
	for(int i = 0 ; i < n ; i++)
	{
		if(a[i] == 'R')
			R++;
		else if(a[i] == 'G')
			G++;
		else if(a[i] == 'B')
			B++;
	}
	
	ssum += R * G * B;
	
	for(int i = 1 ; i < n ; i++)
	{
		for(int j = 0 ; j < n ; j++)
		{
			if(j + i >= n || j + i * 2 >= n)
				break;
			if(a[j] != a[j + i] && a[j + i] != a[j + i * 2] && a[j + i * 2] != a[j])
				ssum--;
		}
	}
	
	printf("%lld", ssum);
	return 0;
}

Measured memory_bytes: 3816
#include <bits/stdc++.h>
using namespace std;
 
#define fst() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define f(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define mp make_pair
#define endl '\n'
#define maxn ((int)1e7)
typedef long long ll;
typedef long double ld;

ll a[200005];
int main()
{ 
  fst();
  int n,i;
  cin>>n;
  f(i,1,n+1)
  {
    cin>>a[i];
    a[i]-=i;
  }
  sort(a+1,a+n+1);
  ll x;
  if(n%2==0) x=(a[n/2]+a[n/2+1])/2;
  else x=a[n/2+1];
  ll ans=0;
  f(i,1,n+1) ans+=abs(a[i]-x);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int a[100010];
bool vis[100010];
int n;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n;
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]!=0)
		{
			vis[i]=true;
			ans+=a[i]/2;
			a[i]%=2;
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]&&a[i+1])
		{
			ans++;
			a[i]=0;
			a[i+1]=0;
		}
		if(a[i-1]&&vis[i]){
			a[i-1]=0;
			a[i]=1;
		}
		if(a[i]&&a[i+1])
		{
			ans++;
			a[i]=0;
			a[i+1]=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 768
r, c = [int(s) for s in input().split()]
rows = [[0 for i in range(c + 1)] for j in range(r + 1)]

for rc in range(r):
    in_row = [int(s) for s in input().split()]
    for cc, val in enumerate(in_row):
        rows[rc][cc] = val
        rows[rc][-1] += val
        rows[-1][cc] += val
        rows[-1][-1] += val
    
for row in rows:
    print(' '.join([str(i) for i in row]))

Measured memory_bytes: 7752
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
    int a[51],n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int tot=0;
    for(int i=n-k+1;i<=n;i++)tot+=a[i];
    cout<<tot<<endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

def main():
    N = int(input())
    a = list(map(int, input().split()))
    arg = round(sum(a) / len(a))
    ans = 0
    for i in range(N):
        ans += (a[i] - arg)**2
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9120
N=int(input())
a=list(map(int,input().split()))
sum=0

for i in a:
  sum+=i
ave=sum//N

var1,var2=0,0
for i in a:
  var1+=(i-ave)**2
  var2+=(i-ave-1)**2
print(min(var1,var2))

Measured memory_bytes: 3060
def sorted_arrays():
	n = int(raw_input())
	a = map(int, raw_input().split(" "))
	if n==1:
		print 1
		return
	ans = 1
	tag=0
	for i in range(1, n):
		if a[i-1]<a[i]:
			if tag==0:
				tag=1
			elif tag==-1:
				ans+=1
				# tag=0 because for the next most left subarray
				# we do not know whether increasing or decreasing
				tag=0
		if a[i-1]>a[i]:
			if tag==0:
				tag=-1
			elif tag==1:
				ans+=1
				tag=0
	print ans

if __name__ == "__main__":
	sorted_arrays()

Measured memory_bytes: 11320
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

A = [x-i for i, x in enumerate(A)]
cnt_A = Counter(A)

ans = 0
for i, a in enumerate(A):
    ans += cnt_A[-A[i]-2*i]
print(ans)


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

int main(){
	int N, M, i, j, k;
	scanf("%d%d", &N, &M);
	vector<int> D(N);
	vector<pair<int, int>> D_id(N);
	for(i = 0; i < N; i++){
		scanf("%d", &D[i]);
		D_id[i].first = D[i];
		D_id[i].second = i;
	}
	vector<vector<int>> g(N, vector<int>(0)), edge_id(N, vector<int>(0));
	for(i = 0; i < M; i++){
		int U, V;
		scanf("%d%d", &U, &V);
		U--;
		V--;
		g[U].push_back(V);
		edge_id[U].push_back(i);
		g[V].push_back(U);
		edge_id[V].push_back(i);
	}
	sort(D_id.begin(), D_id.end());
	vector<int> color(N, -1), C(M, -1);
	for(k = 0; k < N; k++){
		int d = D_id[k].first;
		i = D_id[k].second;
		int equal_less_than_count = 0;
		int O_near = 0;
		for(j = 0; j < g[i].size(); j++){
			if(D[g[i][j]] <= D[i]){
				equal_less_than_count++;
				C[edge_id[i][j]] = d;
			}
			if(color[g[i][j]] == 0){
				O_near = 1;
			}
		}
		if(equal_less_than_count == 0){
			printf("-1\n");
			return 0;
		}
		color[i] = O_near;
	}
	for(i = 0; i < N; i++){
		if(color[i] == 0){
			printf("W");
		}
		else{
			printf("B");
		}
	}
	printf("\n");
	for(i = 0; i < M; i++){
		printf("%d\n", C[i]);
	}
	return 0;
}

Measured memory_bytes: 16896
#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++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define P pair<int, int>
typedef long long ll;
const ll mod = 1e9+7;

//繰り返し自乗法による累乗計算
//a**n
ll pow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = pow(a, n/2);
    return res * res;
  }
  return a * pow(a, n-1);
}
//繰り返し自乗法によるmod累乗計算
//a**n (mod)
ll modpow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = modpow(a, n/2);
    return res * res % mod;
  }
  return a * modpow(a, n-1) % mod;
}
//組み合わせ
//nCa
ll com(ll n, ll a){
  ll x = 1, y = 1;
  rep(i,a){
    x *= n-i;
    y *= i+1;
  }
  ll res = x / y;
  return res;
}
//組み合わせ(mod)
//nCa (mod)
ll modcom(ll n, ll a){
  ll x = 1, y = 1;
  rep(i, a){
    x = x * (n-i) % mod;
    y = y * (i+1) % mod;
  }
  ll ans = x * modpow(y, mod-2) % mod;
  return ans;
}
//gcd 最大公約数
ll gcd(ll x, ll y){
  if(x % y == 0) return y;
  return gcd(y, x%y);
}
//lcm 最小公倍数
ll lcm(ll x, ll y){
  return x * y / gcd(x, y);
}
//ngcd n個の最大公約数
ll ngcd(vector<ll> a){
  ll res;
  res = a[0];
  for(ll i = 1; i < a.size() && res != 1; i++) {
    res = gcd(a[i], res);
  }
  return res;
}
//nlcm n個の最小公倍数
ll nlcm(vector<ll> a) {
  ll res;
  res = a[0];
  for (ll i = 1; i < a.size(); i++) {
    res = lcm(res, a[i]);
  }
  return res;
}
// 素数判定
bool isprime(ll x){
  ll i;
  if(x < 2) return false;
  else if(x == 2) return true;
  if(x % 2 == 0) return false;
  for(i = 3; i*i <= x; i += 2){
    if(x % i == 0) return false;
  }
  return true;
}
// 桁和
ll digsum(ll x){
  ll res = 0;
  while(x > 0){
    res += x % 10;
    x /= 10;
  }
  return res;
}

int main(){
  int a, b;
  string s;
  cin >> a >> b >> s;
  bool ans = true;
  for(int i = 0; i < a; i++){
    if(s[i] < '0' || s[i] > '9') ans = false;
  }
  if(s[a] != '-') ans = false;
  for(int i = a+1; i <= a+b; i++){
    if(s[i] < '0' || s[i] > '9') ans = false;
  }
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-
#D - Static Sushi 
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,C = map(int,readline().split())
#時計回りでの距離X,カロリーV
D = []
V = []
for _ in range(N):
    x,v = map(int,readline().split())
    D.append(x)
    V.append(v)
D.append(C)
V.append(0)
##時計回りでのS1-d1,S1-2*d2の最大値 X1,X2
##反時計回りでのS2-d2,S2-2*d2の最大値 Y1,Y2
X1,X2 = [0],[0]
d = 0 
total = 0
tmp1,tmp2 = 0,0
for i in range(N):
    d = D[i]
    total += V[i]
    tmp1 = max(tmp1,total-d)
    tmp2 = max(tmp2,total-2*d)
    X1.append(tmp1)
    X2.append(tmp2)

m1 = 0
m2 = 0
d = 0 
total = 0
for i in range(N,-1,-1):
    d = (C-D[i])
    total += V[i]
    tmp1 = total - d
    tmp2 = total - 2*d
    m1 = max(m1,tmp1+X2[i])
    m2 = max(m2,tmp2+X1[i])
print(max(m1,m2))

Measured memory_bytes: 91216
#include <iostream>
#include <unordered_map>
#include <iterator>
#include <algorithm>
#include <string>
using namespace std;
#define ALL(a) (a).begin(), (a).end()
const int64_t BIG_PRIME = 1000000007;

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

    if(n/100==7 || (n%100)/10==7 || n%10==7){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 char a;
  char b;
  char c;
char d;
char e;
char f;
char g;
 char h;
char i;
  cin >> a>> b>> c>> d>> e>> f>> g>> h>> i;
char x=a;
char y=e;
char z=i;
  cout << x<< y<< z<< endl;
}
  

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
class UnionFind {
private:
    int sz;
    vector<int> par, size_;
public:
    UnionFind(){}
    UnionFind(int node_size) : sz(node_size), par(sz), size_(sz, 1){
        iota(par.begin(), par.end(), 0);
    }
    int find(int x){
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
    void unite(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return;
        if(size_[x] < size_[y]) swap(x,y);
        par[y] = x;
        size_[x] += size_[y];
    }
    int size(int x){
        x = find(x);
        return size_[x];
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    rep(i,m){
        int a, b;
        cin >> a >> b;
        uf.unite(a-1,b-1);
    }
    int ans = 1;
    rep(i,n)ans = max(ans, uf.size(i));
    cout << ans << endl;
}


Measured memory_bytes: 4700