Cheating, of course :)

Any array can be sorted using no more than $$$\frac{n(n-1)}2$$$ operations. Think or guess when we need exactly $$$\frac{n(n-1)}2$$$ operations.

#include<iostream>

using namespace std;

int a[1000000+5];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        for (int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        bool can=false;
        for (int i=1; i<n; i++)
        {
            if (a[i]>=a[i-1])
            {
                can=true;
                break;
            }
        }
        if (can) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
}

Think of a simple criteria when a_i & a_j >= a_i ^ a_j by considering the bits from highest to lowest. Apply your observations to calculate the answer fast.

#include<iostream>
#include<vector>
#include<algorithm>
#include<ctime>
#include<random>

using namespace std;

mt19937 rnd(time(NULL));

int a[1000000+5];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        for (int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        int64_t ans=0;
        for (int j=29; j>=0; j--)
        {
            int64_t cnt=0;
            for (int i=0; i<n; i++)
            {
                if (a[i]>=(1<<j)&&a[i]<(1<<(j+1)))
                {
                    cnt++;
                }
            }
            ans+=cnt*(cnt-1)/2;
        }
        cout<<ans<<'\n';
    }
}

Use dynamic programming.

#include <iostream>
#include <vector>

using namespace std;

inline int64_t calc(const vector<int> &a) {
	int n = a.size();
	vector<int64_t> d1(n+1), d2(n+1);
	d1[0] = -static_cast<int64_t>(1e18);
	d2[0] = 0;
	for (int i = 0; i < n; ++i) {
		d1[i+1] = max(d1[i], d2[i] + a[i]);
		d2[i+1] = max(d2[i], d1[i] - a[i]);
	}
	return max(d1.back(), d2.back());
}

int main() {
	ios_base::sync_with_stdio(false);
	int t; cin >> t;
	while (t--) {
		int n, q; cin >> n >> q;
		vector<int> a(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
		}
		cout << calc(a) << "\n";
		for (int i = 0; i < q; ++i) {
			int l, r; cin >> l >> r; --l; --r;
			swap(a[l], a[r]);
			cout << calc(a) << "\n";
		}
	}
	return 0;
}

The dynamic programming doesn't work here. Consider taking only local minima and maxima and think whether we need to take something else.

import java.io.*;
import java.util.*;

public class C2_Java {
    int[] a;
    int n;
    long ans;
    
    void add(int i, int sign) {
        if (i == 0 || i == n+1) return;
        if (a[i-1] < a[i] && a[i] > a[i+1]) ans += sign * a[i];
        if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= sign * a[i];
    }
    
    void addTwo(int l, int r, int sign) {
        if (l == r) return;
        if (l+1 == r) {
            add(l-1, sign);
            add(l, sign);
            add(r, sign);
            add(r+1, sign);
            return;
        }
        add(l-1, sign);
        add(l, sign);
        add(l+1, sign);
        if (l+2 != r) add(r-1, sign);
        add(r, sign);
        add(r+1, sign);
    }
    
    public void run() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer tok = new StringTokenizer(in.readLine());
        int t = Integer.parseInt(tok.nextToken());
        while (t --> 0) {
            tok = new StringTokenizer(in.readLine());
            n = Integer.parseInt(tok.nextToken());
            int q = Integer.parseInt(tok.nextToken());
            a = new int[n + 2];
            tok = new StringTokenizer(in.readLine());
            for (int i = 1; i <= n; ++i) {
                a[i] = Integer.parseInt(tok.nextToken());
            }
            a[0] = -1;
            a[n+1] = -1;
            ans = 0;
            StringBuilder builder = new StringBuilder();
            for (int i = 1; i <= n; ++i) {
                if (a[i-1] < a[i] && a[i] > a[i+1]) ans += a[i];
                if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= a[i];
            }
            builder.append(ans).append("\n");
            while (q --> 0) {
                tok = new StringTokenizer(in.readLine());
                int l = Integer.parseInt(tok.nextToken());
                int r = Integer.parseInt(tok.nextToken());
                if (l == r) {
                    builder.append(ans).append("\n");
                    continue;
                }
                addTwo(l, r, -1);
                int tmp = a[l];
                a[l] = a[r];
                a[r] = tmp;
                addTwo(l, r, +1);
                builder.append(ans).append("\n");
            }
            out.write(builder.toString());   
        }
        
        in.close();
        out.close();        
    }

    public static void main(String[] args) throws IOException {
        (new C2_Java()).run();
    }
}

#include<iostream>

using namespace std;

#define int long long

int a[1000000+5];

int n;

int ans=0;

inline void insert(int i)
{
    if (i==0||i==n+1) return;
    if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];
    if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];
}

inline void erase(int i)
{
    if (i==0||i==n+1) return;
    if (a[i-1]<a[i]&&a[i]>a[i+1]) ans-=a[i];
    if (a[i-1]>a[i]&&a[i]<a[i+1]) ans+=a[i];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int q;
        cin>>n>>q;
        for (int i=1; i<=n; i++)
        {
            cin>>a[i];
        }
        a[0]=-1;
        a[n+1]=-1;
        ans=0;
        for (int i=1; i<=n; i++)
        {
            if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];
            if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];
        }
        cout<<ans<<'\n';
        while (q--)
        {
            int l,r;
            cin>>l>>r;
            erase(l-1);
            erase(l);
            erase(l+1);
            if (l!=r)
            {
                if (r-1!=l+1&&r-1!=l) erase(r-1);
                if (r!=l+1) erase(r);
                erase(r+1);
            }
            swap(a[l],a[r]);
            insert(l-1);
            insert(l);
            insert(l+1);
            if (l!=r)
            {
                if (r-1!=l+1&&r-1!=l) insert(r-1);
                if (r!=l+1) insert(r);
                insert(r+1);
            }
            cout<<ans<<'\n';
        }
    }
}

The intersection of any $$$k$$$ segments is either empty or is a segment. Let's fix the left bound of the intersection and calculate the number of sets of $$$k$$$ segments such that their intersection starts in this left bound.

import java.io.*;
import java.util.*;

public class D_Java {
	public static final int MOD = 998244353;
	
	public static int mul(int a, int b) {
		return (int)((long)a * (long)b % MOD);
	}
	
	int[] f;
	int[] rf;
	
	public int C(int n, int k) {
		return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k]));
	}
	
	public static int pow(int a, int n) {
		int res = 1;
		while (n != 0) {
			if ((n & 1) == 1) {
				res = mul(res, a);
			}
			a = mul(a, a);
			n >>= 1;
		}
		return res;
	}
	
	static void shuffleArray(int[] a) {
		Random rnd = new Random();
		for (int i = a.length-1; i > 0; i--) {
			int index = rnd.nextInt(i + 1);
			int tmp = a[index];
			a[index] = a[i];
			a[i] = tmp;
		}
	}
	
	public static int inv(int a) {
		return pow(a, MOD-2);
	}
	
	public void doIt() throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tok = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(tok.nextToken());
		int k = Integer.parseInt(tok.nextToken());
		
		f = new int[n+42];
		rf = new int[n+42];
		f[0] = rf[0] = 1;
		for (int i = 1; i < f.length; ++i) {
			f[i] = mul(f[i-1], i);
			rf[i] = mul(rf[i-1], inv(i));
		}
		
		int[] events = new int[2*n];
		for (int i = 0; i < n; ++i) {
			tok = new StringTokenizer(in.readLine());
			int le = Integer.parseInt(tok.nextToken());
			int ri = Integer.parseInt(tok.nextToken());
			events[i] = le*2;
			events[i + n] = ri*2 + 1;
		}
		shuffleArray(events);
		Arrays.sort(events);
		
		int ans = 0;
		int balance = 0;
		for (int r = 0; r < 2*n;) {
			int l = r;
			while (r < 2*n && events[l] == events[r]) {
				++r;
			}
			int added = r - l;
			if (events[l] % 2 == 0) {
				// Open event
				ans += C(balance + added, k);
				if (ans >= MOD) ans -= MOD;
				ans += MOD - C(balance, k);
				if (ans >= MOD) ans -= MOD;
				balance += added;
			} else {
				// Close event
				balance -= added;
			}
		}
		
		in.close();
		System.out.println(ans);
	}
	
	public static void main(String[] args) throws IOException {
		(new D_Java()).doIt();
	}
}

Let's keep the number of zeroes between any pair consecutive ones instead of the original array of zeroes and ones. How will the swap operation look in this case. How to calculate the protection?

Suppose we have the initial array and the final array. Think of the number of operations you need to make the first one equal to the second one.

Join all your observations together and use DP.

#include <cassert>
#include <climits>
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

template<typename T>
inline void umin(T &a, const T &b) {
	a = min(a, b);
}

template<typename T>
inline void umax(T &a, const T &b) {
	a = max(a, b);
}

int main() {
	ios_base::sync_with_stdio(false);
	
	int n; cin >> n;
	vector<int> a(n);
	for (int &x : a) {
		cin >> x;
	}
	a.push_back(1);
	
	vector<int> gg;
	for (int i = 0; i <= n; ++i) {
		int s = i;
		while (a[i] == 0) ++i;
		gg.push_back(i - s);
	}
	
	vector<int> p = gg;
	partial_sum(begin(p), end(p), begin(p));
	
	constexpr int mx = 103;
	constexpr int dx = mx + 1, dy = mx + 1, dz = mx * (mx + 1) / 2 + 1;
	static int dp[dx][dy][dz] = {};
	
	for (int i = 0; i < dx; ++i) {
		for (int j = 0; j < dy; ++j) {
			for (int k = 0; k < dz; ++k) {
				dp[i][j][k] = INT_MAX;
			}
		}
	}
	dp[0][0][0] = 0;
	
	int k = gg.size(), l = p.back();
	for (int i = 0; i < k; ++i) {
		for (int j = 0; j <= l; ++j) {
			for (int s = 0; s <= n * (n-1) / 2; ++s) {
				if (dp[i][j][s] == INT_MAX) continue;
				for (int q = j; q <= l; ++q) {
					umin(dp[i+1][q][s + abs(q - p[i])], dp[i][j][s] + (q-j)*(q-j));
				}
			}
		}
	}
	
	int mn = INT_MAX;
	for (int s = 0; s <= n * (n-1) / 2; ++s) {
		umin(mn, dp[k][l][s]);
		int val = l*l - mn;
		assert(val % 2 == 0);
		cout << val/2 << " ";
	}
	cout << endl;
	
	return 0;
}

program sum;

{$Mode Delphi}

uses
  gmp;

var
  sa, sb: string;
  a, b: MPInteger;
begin
  readLn(sa);
  readLn(sb);
  a := sa; b := sb;
  writeLn(string(a + b));
end.

program F;

{$mode objfpc}{$h+}
{$optimization LEVEL3}

uses gmp;

var
  num: string;
  mpNum: MPInteger;
  root, rem: MPInteger;
begin
  readLn(num);
  mpNum := num;
  mpNum := mpNum - 1;
  z_sqrtrem(root, rem, mpNum);
  if rem < root then begin
    writeln(string(rem + 1));
  end else begin
    writeln(string(2 * root + 1 - rem));
  end;
end.

404 Not Found

#include <iostream>
#include <map>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	map<string, int> vals;
	vals["Tetrahedron"]  = 4;
	vals["Cube"]         = 6;
	vals["Octahedron"]   = 8;
	vals["Dodecahedron"] = 12;
	vals["Icosahedron"]  = 20;
	int n; cin >> n;
	int res = 0;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		res += vals[s];
	}
	cout << res << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class PolyhedronSums {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		HashMap<String, Integer> vals = new HashMap<String, Integer>();
		vals.put("Tetrahedron", 4);
		vals.put("Cube", 6);
		vals.put("Octahedron", 8);
		vals.put("Dodecahedron", 12);
		vals.put("Icosahedron", 20);
		int n = Integer.parseInt(reader.readLine());
		int res = 0;
		for (int i = 0; i < n; i++) {
			res += vals.get(reader.readLine());
		}	
		writer.write(Integer.toString(res));
		reader.close();
		writer.close();
	}
}

vals = {
	'Tetrahedron': 4,
	'Cube': 6,
	'Octahedron': 8,
	'Dodecahedron': 12,
	'Icosahedron': 20
}

n = int(input())
ans = 0
for i in range(0, n):
	ans += vals[input()]
print(ans)

Think of what periods to take if Anton attends chess classes earlier than programming classes and vice versa.

#include <iostream>
#include <algorithm>

const int infinity = 1234567890;

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int n; cin >> n;
	vector<pair<int, int> > a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	int m; cin >> m;
	vector<pair<int, int> > b(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i].first >> b[i].second;
	}
	int minR1 = infinity, maxL1 = -infinity;
	int minR2 = infinity, maxL2 = -infinity;
	for (int i = 0; i < n; i++) {
		maxL1 = max(maxL1, a[i].first);
		minR1 = min(minR1, a[i].second);	
	}
	for (int i = 0; i < m; i++) {
		maxL2 = max(maxL2, b[i].first);
		minR2 = min(minR2, b[i].second);	
	}
	int res = max(maxL2 - minR1, maxL1 - minR2);
	cout << max(res, 0) << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class TwoSegments {
	public static final int infinity = 1234567890;
	
	public static class Segment {
		public int l;
		public int r;

		public Segment(int aL, int aR) {
			l = aL;
			r = aR;
		} 
	}
	
	private static Segment[] readList(BufferedReader reader) throws Exception {
		int n = Integer.parseInt(reader.readLine());
		Segment[] res = new Segment[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());		
			int l = Integer.parseInt(tokenizer.nextToken());
			int r = Integer.parseInt(tokenizer.nextToken());
			res[i] = new Segment(l, r);
		}
		return res;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		Segment[] a = readList(reader);
		Segment[] b = readList(reader);
		int minR1 = infinity, maxL1 = -infinity;
		int minR2 = infinity, maxL2 = -infinity;
		for (int i = 0; i < a.length; i++) {
			maxL1 = Math.max(maxL1, a[i].l);
			minR1 = Math.min(minR1, a[i].r);	
		}
		for (int i = 0; i < b.length; i++) {
			maxL2 = Math.max(maxL2, b[i].l);
			minR2 = Math.min(minR2, b[i].r);	
		}
		int res = Math.max(maxL2 - minR1, maxL1 - minR2);
		writer.write(Integer.toString(Math.max(res, 0)));
		reader.close();
		writer.close();
	}
}

infinity = 1234567890
minR1 = minR2 = infinity
maxL1 = maxL2 = -infinity
n = int(input())
for i in range(0, n):
	(l, r) = map(int, input().split())
	maxL1 = max(maxL1, l)
	minR1 = min(minR1, r)
m = int(input())
for i in range(0, m):
	(l, r) = map(int, input().split())
	maxL2 = max(maxL2, l)
	minR2 = min(minR2, r)
res = max(maxL2 - minR1, maxL1 - minR2);
print(max(res, 0))

Model the process to determine how the number of corns in the barn changes.

#include <iostream>
#include <cstdint>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int64_t n, m;
	cin >> n >> m;
	if (n <= m) {
		cout << n << endl;
	} else {
		n -= m;
		int64_t l = 0, r = 2e9;
		while (l < r) {
			int64_t m = (l + r) / 2;
			int64_t val = m * (m+1) / 2;
			if (val >= n) {
				r = m;
			} else {
				l = m+1;
			}
		}
		cout << l + m << endl;
	}
	return 0;
}

import java.io.*;
import java.util.*;

public class SparrowsJava {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		long n = Long.parseLong(tokenizer.nextToken());
		long m = Long.parseLong(tokenizer.nextToken());	
		if (n <= m) {
			writer.write(Long.toString(n));
		} else {
			n -= m;
			long l = 0, r = (long)2e9;
			while (l < r) {
				long med = (l + r) / 2;
				long val = med * (med+1) / 2;
				if (val >= n) {
					r = med;
				} else {
					l = med+1;
				}
			}
			writer.write(Long.toString(l + m));
		}
		reader.close();
		writer.close();
	}
}

(n, m) = map(int, input().split())
if n <= m:
	print(n)
else:
	aM = m
	n -= m
	(l, r) = (0, int(2e9))
	while l < r:
		m = (l + r) // 2;
		val = m * (m+1) // 2;
		if val >= n:
			r = m
		else:
			l = m+1
	print(l + aM)

Solve a simplified version of the problem. Let our sequence first contains x opening brackets and then contains y closing brackets, and the last opening bracket must necessarily appear in our RSBS. Use a naive solution to see how the answer looks. Think what to do next.

#include <iostream>
#include <vector>
#include <cstdint>

using namespace std;

int mod = (int)1e9 + 7;

int64_t extGcd(int64_t a, int64_t b, int64_t& x, int64_t& y) { 
	if (!a) {
		x = 0;
		y = 1;
		return b;
	}
	int64_t x1, y1;
	int64_t d = extGcd(b % a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

inline int addMod(int a, int b, int m = mod) {
	return ((int64_t)a + b) % m;
}

inline int mulMod(int a, int b, int m = mod) {
	return ((int64_t)a * b) % m;
}

inline int divMod(int a, int b, int m = mod) {
	int64_t x, y;
	int64_t g = extGcd(b, m, x, y);
	if (g != 1) {
		cerr << "Bad gcd!" << endl;
		for (;;);
	}
	x = (x % m + m) % m;
	return mulMod(a, x, m);
}

const int factRange = 1000000;
int fact[factRange];

inline void precalcFactorials() {
	fact[0] = 1;
	for (int i = 1; i < factRange; i++) {
		fact[i] = mulMod(fact[i-1], i);
	}
}

inline int F(int n) {
	return (n < 0) ? 0 : fact[n];
}

inline int C(int k, int n) {
	return divMod(F(n), mulMod(F(n-k), F(k)));
}

int main() {
	ios_base::sync_with_stdio(false);
	string s; 
	cin >> s;
	int len = s.size();
	precalcFactorials();
	vector<int> opnLeft(len), clsRight(len);
	opnLeft[0] = (s[0] == '(') ? 1 : 0;
	for (int i = 1; i < len; i++) {
		opnLeft[i] = opnLeft[i-1] + ((s[i] == '(') ? 1 : 0);
	}
	clsRight[len-1] = (s[len-1] == ')') ? 1 : 0;
	for (int i = len-2; i >= 0; i--) {
		clsRight[i] = clsRight[i+1] + ((s[i] == ')') ? 1 : 0);
	}
	int res = 0;
	for (int i = 0; i < len; i++) {
		if (s[i] != '(' || clsRight[i] == 0) {
			continue;
		}
		int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);
		res = addMod(res, add);
	}
	cout << res << endl;
	return 0;
}

import java.io.*;
import java.util.*;

public class BracketsJava {
	public static int mod = (int)1e9 + 7;
	
	public static class ExtGcdResult {
		long x;
		long y;
	}
	
	public static long extGcd(long a, long b, ExtGcdResult res) { 
		if (a == 0) {
			res.x = 0L;
			res.y = 1L;
			return b;
		}
		ExtGcdResult newRes = new ExtGcdResult();
		long d = extGcd(b % a, a, newRes); 
		res.x = newRes.y - (b / a) * newRes.x;
		res.y = newRes.x;
		return d; 
	}
	
	public static final int addMod(int a, int b) { 
		return (int)(((long)a + b) % mod); 
	}

	public static final int mulMod(int a, int b) { 
		return (int)(((long)a * b) % mod); 
	}
	
	public static final int divMod(int a, int b) { 
		ExtGcdResult res = new ExtGcdResult();
		long g = extGcd(b, mod, res); 
		if (g != 1) {
			System.out.println("Bad gcd!");
			for (;;);
		}
		int q = (int)((res.x % mod + mod) % mod); 
		return mulMod(a, q); 
	}
	
	public static final int[] precalcFactorials() {
		int[] fact = new int[factRange];
		fact[0] = 1;
		for (int i = 1; i < factRange; i++) {
			fact[i] = mulMod(fact[i-1], i);
		}
		return fact;
	}

	public static final int factRange = 1000000;
	public static final int[] fact = precalcFactorials();
	
	public static final int F(int n) {
		return (n < 0) ? 0 : fact[n];
	}
	
	public static final int C(int k, int n) {
		int res = divMod(F(n), mulMod(F(n-k), F(k)));
		return divMod(F(n), mulMod(F(n-k), F(k)));
	} 
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		String s = reader.readLine();
		int len = s.length();
		int[] opnLeft = new int[len], clsRight = new int[len];
		opnLeft[0] = (s.charAt(0) == '(') ? 1 : 0;
		for (int i = 1; i < len; i++) {
			opnLeft[i] = opnLeft[i-1] + ((s.charAt(i) == '(') ? 1 : 0);
		}
		clsRight[len-1] = (s.charAt(len-1) == ')') ? 1 : 0;
		for (int i = len-2; i >= 0; i--) {
			clsRight[i] = clsRight[i+1] + ((s.charAt(i) == ')') ? 1 : 0);
		}
		int res = 0;
		for (int i = 0; i < len; i++) {
			if (s.charAt(i) != '(' || clsRight[i] == 0) {
				continue;
			}
			int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1);
			res = addMod(res, add);
		}		
		writer.write(Integer.toString(res));
		reader.close();
		writer.close();		
	}
}

Divide all the queries in blocks. Then divide the positions to the mobile (those ones that will change in this block) and immoblile. Think what to do next.

// Thanks to netman for the idea for this wonderful solution :)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
#include <algorithm>

using namespace std;

class SQRTDecomposition {
	private:
		int n, sz;
		vector<int> val;
		vector<int> blocks;
	public:
		inline void add(int v, int delta) {
			val[v] += delta;
			blocks[v / sz] += delta;
		}
		
		inline int sum(int l, int r) {	
			if (l < 0) {
				l = 0;
			}
			if (r >= n) {
				r = n;
			}
			r++;
			int res = 0;
			int lBlock = (l + sz - 1) / sz, rBlock = r / sz;
			for (int i = lBlock; i < rBlock; i++) {
				res += blocks[i];
			}
			int lBlockR = lBlock * sz, rBlockR = rBlock * sz;
			if (lBlockR >= rBlockR) {
				for (int i = l; i < r; i++) {
					res += val[i];
				}
			} else {
				for (int i = l; i < lBlockR; i++) {
					res += val[i];
				}
				for (int i = rBlockR; i < r; i++) {
					res += val[i];
				}
			}
			return res;
		}
		
		inline void clear() {
			val.assign(val.size(), 0);
			blocks.assign(blocks.size(), 0);
		}
		
		SQRTDecomposition(int n, int sz)
			: n(n), sz(sz), val(n, 0), blocks((n + sz - 1) / sz, 0) {
		}
};

struct ToProcess {
	int x, y1, y2, sgn, id;
};

const int BLOCK_SZ_Q = 256;
const int BLOCK_SZ_N = 512;
const int MAX_N = 200000;

int n, q;
vector<ToProcess> sortedL[MAX_N], sortedR[MAX_N];
SQRTDecomposition sum(MAX_N, BLOCK_SZ_N);
int64_t ans[MAX_N], preAns[MAX_N];
pair<int, int> queries[MAX_N];
vector<int> goods;
int p[MAX_N];
bool good[MAX_N];

inline void add(int q, int sgn, int id) {
	if (q-1 >= 0) {
		sortedL[q-1].push_back({q-1, p[q]+1, n-1, sgn, id});
	}
	if (q+1 < n) {
		sortedR[q+1].push_back({q+1, 0, p[q]-1, sgn, id});
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		p[i] = i;
	}
	for (int i = 0; i < q; i++) {
		cin >> queries[i].first >> queries[i].second;
		queries[i].first--; queries[i].second--;
	}
	int64_t cnt = 0;
	for (int i = 0; i < q; i += BLOCK_SZ_Q) {
		int iEnd = min(q, i + BLOCK_SZ_Q);
		for (int j = 0; j < n; j++) {
			good[j] = false;
		}
		for (int j = i; j < iEnd; j++) {
			good[queries[j].first] = true;
			good[queries[j].second] = true;
		}
		goods.clear();
		for (int j = 0; j < n; j++) {
			if (good[j]) {
				goods.push_back(j);
			}
		}
		int64_t goodCnt = 0;
		for (int j = 0; j < n; j++) {
			sortedL[j].clear();
			sortedR[j].clear();
		}
		for (int j = i; j < iEnd; j++) {
			int a = queries[j].first, b = queries[j].second;
			if (a == b) {
				ans[j] += goodCnt;
				continue;
			}
			for (int k = 0; k < (int)goods.size(); k++) {
				int q = goods[k];
				if (q == a || q == b) {
					continue;
				}
				if ((p[q] < p[a] && q > a) ||
				    (p[q] > p[a] && q < a)) {
					goodCnt--;
				}
				if ((p[q] < p[b] && q > b) ||
				    (p[q] > p[b] && q < b)) {
					goodCnt--;
				}
				if ((p[q] < p[b] && q > a) ||
				    (p[q] > p[b] && q < a)) {
					goodCnt++;
				}
				if ((p[q] < p[a] && q > b) ||
				    (p[q] > p[a] && q < b)) {
					goodCnt++;
				}
			}
			if ((a < b && p[a] > p[b]) ||
				(a > b && p[a] < p[b])) {
				goodCnt--;
			} else {
				goodCnt++;
			}
			ans[j] += goodCnt;
			add(a, -1, j);
			add(b, -1, j);
			swap(p[a], p[b]);
			add(a, +1, j);
			add(b, +1, j);
		}
		sum.clear();
		for (int j = 0; j < n; j++) {
			if (!good[j]) {
				sum.add(p[j], 1);
			}
			for (int k = 0; k < (int)sortedL[j].size(); k++) {
				ToProcess &cur = sortedL[j][k];
				int64_t res = sum.sum(cur.y1, cur.y2);
				res *= cur.sgn;
				preAns[cur.id] += res;
			}
		}
		sum.clear();
		for (int j = n-1; j >= 0; j--) {
			if (!good[j]) {
				sum.add(p[j], 1);
			}
			for (int k = 0; k < (int)sortedR[j].size(); k++) {
				ToProcess &cur = sortedR[j][k];
				int64_t res = sum.sum(cur.y1, cur.y2);
				res *= cur.sgn;
				preAns[cur.id] += res;
			}
		}
		for (int j = i; j < iEnd; j++) {
			if (j != i) {
				preAns[j] += preAns[j-1];	
			}
			ans[j] += cnt + preAns[j];
		}
		cnt = ans[iEnd - 1];
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}

import java.io.*;
import java.util.*;

public class InversionNSqrtNNoVectors {
	private static final int BLOCK_SZ_Q = 256;
	private static final int BLOCK_SZ_N = 512;
	
	public static class ToProcess {
		public int x, y1, y2, sgn, id;
		
		public void set(int pX, int pY1, int pY2, int pSgn, int pId) {
			x = pX;
			y1 = pY1;
			y2 = pY2;
			sgn = pSgn;
			id = pId;
		}
		
		public ToProcess() {
		}
	}
	
	public static class ToProcessCompareAsc implements Comparator<ToProcess> {
		@Override
		public int compare(ToProcess o1, ToProcess o2) {
			return o1.x - o2.x;
		}
	}
	
	public static class ToProcessCompareDesc implements Comparator<ToProcess> {
		@Override
		public int compare(ToProcess o1, ToProcess o2) {
			return o2.x - o1.x;
		}
	}
	
	static int n, q;
	static int[] p;
	static ToProcess[] queryL, queryR;
	static int queryLCnt, queryRCnt;
	static SQRTDecomposition sum;
	static ToProcessCompareAsc ascCmp = new ToProcessCompareAsc();
	static ToProcessCompareDesc descCmp = new ToProcessCompareDesc();
	
	public static final void add(int q, int sgn, int id) {
		if (q-1 >= 0) {
			queryL[queryLCnt++].set(q-1, p[q]+1, n-1, sgn, id);
		}
		if (q+1 < n) {
			queryR[queryRCnt++].set(q+1, 0, p[q]-1, sgn, id);
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		n = Integer.parseInt(tokenizer.nextToken());
		q = Integer.parseInt(tokenizer.nextToken());
		int[] qL = new int[q], qR = new int[q];
		long[] ans = new long[q], preAns = new long[q];
		p = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
		for (int i = 0; i < q; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			qL[i] = Integer.parseInt(tokenizer.nextToken()) - 1;
			qR[i] = Integer.parseInt(tokenizer.nextToken()) - 1;
		}
		long cnt = 0;
		boolean[] good = new boolean[n];
		int[] goods = new int[n];
		int goodsSize = 0;
		queryL = new ToProcess[4 * BLOCK_SZ_Q]; queryR = new ToProcess[4 * BLOCK_SZ_Q];
		for (int j = 0; j < 4 * BLOCK_SZ_Q; j++) {
			queryL[j] = new ToProcess();
			queryR[j] = new ToProcess();
		}
		SQRTDecomposition sum = new SQRTDecomposition(n, BLOCK_SZ_N);
		for (int i = 0; i < q; i += BLOCK_SZ_Q) {
			int iEnd = Math.min(q, i + BLOCK_SZ_Q);
			Arrays.fill(good, false);
			for (int j = i; j < iEnd; j++) {
				good[qL[j]] = true;
				good[qR[j]] = true;
			}
			goodsSize = 0;
			for (int j = 0; j < n; j++) {
				if (good[j]) {
					goods[goodsSize++] = j;
				}
			}
			long goodCnt = 0;
			queryLCnt = 0;
			queryRCnt = 0;
			for (int j = i; j < iEnd; j++) {
				int a = qL[j], b = qR[j];
				if (a == b) {
					ans[j] += goodCnt;
					continue;
				}
				for (int k = 0; k < goodsSize; k++) {
					int q = goods[k];
					if (q == a || q == b) {
						continue;
					}
					if ((p[q] < p[a] && q > a) ||
						(p[q] > p[a] && q < a)) {
						goodCnt--;
					}
					if ((p[q] < p[b] && q > b) ||
						(p[q] > p[b] && q < b)) {
						goodCnt--;
					}
					if ((p[q] < p[b] && q > a) ||
						(p[q] > p[b] && q < a)) {
						goodCnt++;
					}
					if ((p[q] < p[a] && q > b) ||
						(p[q] > p[a] && q < b)) {
						goodCnt++;
					}
				}
				if ((a < b && p[a] > p[b]) ||
					(a > b && p[a] < p[b])) {
					goodCnt--;
				} else {
					goodCnt++;
				}
				ans[j] += goodCnt;
				add(a, -1, j);
				add(b, -1, j);
				int tmp = p[a];
				p[a] = p[b];
				p[b] = tmp;
				add(a, +1, j);
				add(b, +1, j);
			}
			sum.clear();
			Arrays.sort(queryL, 0, queryLCnt, ascCmp);
			int curL = 0;
			for (int j = 0; j < n; j++) {
				if (!good[j]) {
					sum.add(p[j], 1);
				}
				for (; curL < queryLCnt; curL++) {
					ToProcess cur = queryL[curL];
					if (cur.x != j) {
						break;
					}
					int res = sum.sum(cur.y1, cur.y2);
					res *= cur.sgn;
					preAns[cur.id] += res;
				}
			}
			sum.clear();
			Arrays.sort(queryR, 0, queryRCnt, descCmp);
			int curR = 0;
			for (int j = n-1; j >= 0; j--) {
				if (!good[j]) {
					sum.add(p[j], 1);
				}
				for (; curR < queryRCnt; curR++) {
					ToProcess cur = queryR[curR];
					if (cur.x != j) {
						break;
					}
					int res = sum.sum(cur.y1, cur.y2);
					res *= cur.sgn;
					preAns[cur.id] += res;
				}
			}
			for (int j = i; j < iEnd; j++) {
				if (j != i) {
					preAns[j] += preAns[j-1];	
				}
				ans[j] += cnt + preAns[j];
			}
			cnt = ans[iEnd - 1];
		}
		for (int i = 0; i < q; i++) {
			writer.write(Long.toString(ans[i]));
			writer.newLine();
		}
		reader.close();
		writer.close();
	}
}

class SQRTDecomposition {
	private int n;
	private int sz;
	private int[] val;
	private int[] blocks;
	
	public final void add(int v, int delta) {
		val[v] += delta;
		blocks[v / sz] += delta;
	}
		
	public final int sum(int l, int r) {	
		if (l < 0) {
			l = 0;
		}
		if (r >= n) {
			r = n;
		}
		r++;
		int res = 0;
		int lBlock = (l + sz - 1) / sz, rBlock = r / sz;
		for (int i = lBlock; i < rBlock; i++) {
			res += blocks[i];
		}
		int lBlockR = lBlock * sz, rBlockR = rBlock * sz;
		if (lBlockR >= rBlockR) {
			for (int i = l; i < r; i++) {
				res += val[i];
			}
		} else {
			for (int i = l; i < lBlockR; i++) {
				res += val[i];
			}
			for (int i = rBlockR; i < r; i++) {
				res += val[i];
			}
		}
		return res;
	}
	
	public void clear() {
		Arrays.fill(val, 0);
		Arrays.fill(blocks, 0);
	}
		
	SQRTDecomposition(int pN, int pSz) {
		n = pN;
		sz = pSz;
		val = new int[n];
		blocks = new int[(n + sz - 1) / sz];
	}
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <iomanip>

#define sqr(a) (a)*(a)
#define all(a) (a).begin(), (a).end()
using namespace std;

template <typename T>
T next_int() {
    T ans = 0, t = 1;
    char ch;
    do { ch = getchar(); } while(ch <= ' ') ;
    if(ch == '-') {
        t = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        ans = ans * 10 + (ch - '0');
        ch = getchar();
    }
    return ans * t;
}

string next_token() {
    char ch;
    string ans = "";
    do { ch = getchar(); } while(ch <= ' ') ;
    while(ch >= ' ') {
        ans += ch;
        ch = getchar();
    }
    return ans;
}

const long long INF = (long long)1e18 + 227 + 1;
const int INFINT = (int)1e9 + 227 + 1;
const int MAXN = (int)2e5 + 227 + 1;
const int MOD = (int)1e9 + 7;
const long double EPS = 1e-9;

long long bin_pow(long long n, long long k) {
    if(!k) return 1;
    long long ans = bin_pow(n, k / 2);
    ans = ans * ans % MOD;
    if(k % 2) ans = ans * n % MOD;
    return ans;
}

struct tree {
    int size_block;
    int len; 
 
    tree(int len) : len(len) {
        size_block = sqrt(len);
 
        kek.resize(len / size_block + 1, vector<int>(size_block, 0));
 
        pr_block.resize(len / size_block + 1, 0);
    }
 
    vector<int> pr_block;
    vector<vector<int> > kek;
 
    void inc(int pos, int num) {
        int x = pos / size_block;
 
        for(int i = pos % size_block; i < size_block; i++) {
            kek[x][i] += num;
        }
 
        for(int i = 0; i <= len / size_block; i++)
            if(i == 0) {
                pr_block[i] = kek[i][size_block - 1];
            } else {
                pr_block[i] = pr_block[i - 1] + kek[i][size_block - 1]; 
            }
    }
 
    int f(int a) {
        return a / size_block;
    }
 
    long long get(vector<int> &a, int l, int r, bool ok = 1) {
        if(ok == 1) {
            l %= size_block;
            r %= size_block;
        }
 
        return a[r] - (l ? a[l - 1] : 0);
    }
 
    int get(int l, int r) {
        if(l > r) return 0;

        r = min(r, len);
  
        if(f(l) == f(r))
            return get(kek[f(l)], l, r);
     
        int ans = 0;
 
        if(l % size_block) {
            ans += get(kek[f(l)], l, size_block - 1);
 
            l += size_block - l % size_block;
        }
 
        if(r % size_block != size_block - 1) {
            ans += get(kek[f(r)], 0, r);
 
            r -= r % size_block + 1;
        }
 
        ans += get(pr_block, f(l), f(r), 0);
 
        return ans;
    }
 
    int get_pref(int p) {
        return get(1, p - 1);
    }

    int get_suff(int p) {
        return get(p + 1, len);
    }
} ;

struct mda {
    vector<int> a;
    vector<tree> t;
    int len, sz;
    long long ans;

    mda(int len) : len(len) {
        sz = 2000;
        ans = 0;

        a.resize(len + 1);
        for(int i = 1; i <= len; i++)
            a[i] = i;

        for(int i = 1; i <= len; i += sz) {
            t.push_back(tree(len));
            for(int j = i; j < i + sz && j <= len; j++)
                add(j, j);
        }
    }

    int get_pref(int L, int R, int k) {
        int ans = 0;

        for(int l = 1; l <= R; l += sz) {
            int r = l + sz - 1;

            if(r < L || l > R) continue;

            if(L <= l && r <= R)
                ans += t[(l - 1) / sz].get_pref(k);
            else
                for(int i = max(l, L); i <= min(r, R); i++) 
                    ans += (a[i] < k);
        }

        return ans;
    }

    int get_suff(int L, int R, int k) {
        int ans = 0;

        for(int l = 1; l <= R; l += sz) {
            int r = l + sz - 1;

            if(r < L || l > R) continue;

            if(L <= l && r <= R)
                ans += t[(l - 1) / sz].get_suff(k);
            else
                for(int i = max(l, L); i <= min(r, R); i++) 
                    ans += (a[i] > k);
        }

        return ans;
    }

    void del(int p, int k) {
        p = (p - 1) / sz;
        t[p].inc(k, -1);
    }

    void add(int p, int k) {
        p = (p - 1) / sz;
        t[p].inc(k, 1);
    }

    void sw(int i, int j) {
        if(i == j) return;
        if(i > j) swap(i, j);

        ans -= get_pref(i, j, a[i]);
        ans -= get_suff(i, j, a[j]);

        if(a[i] > a[j]) ans++;

        del(i, a[i]);
        del(j, a[j]);
        swap(a[i], a[j]);
        add(i, a[i]);
        add(j, a[j]);

        ans += get_pref(i, j, a[i]);
        ans += get_suff(i, j, a[j]);

        if(a[i] > a[j]) ans--;
    }
} ;

int main() {
    // freopen(".in", "r", stdin);

    int n, m; cin >> n >> m;

    mda t(n);

    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;

        t.sw(x, y);
        
        cout << t.ans << "\n";
    }
}

import java.io.*;
import java.util.*;

public class NsqrtNlogNnetman implements Runnable {
    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
        InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in), 32768);
            tokenizer = null;
        }
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static class Fenwick {
        int[] ft;
        Fenwick(int n) {
            ft = new int[n];
        }
        void add(int r, int val) {
            while (r < ft.length) {
                ft[r] += val;
                r |= r + 1;
            }
        }
        int sum(int r) {
            int res = 0;
            while (r >= 0) {
                res += ft[r];
                r = (r & (r + 1)) - 1;
            }
            return res;
        }
        void clear() {
            Arrays.fill(ft, 0);
        }
    }

    static class Query {
        int x, bound, sign, id;
        Query(int x, int bound, int sign, int id) {
            this.x = x;
            this.bound = bound;
            this.sign = sign;
            this.id = id;
        }
    }

    static void getOnPrefSmaller(List<Query> qrs, int r, int y, int id, int sign) {
        qrs.add(new Query(r, y, sign, id));
    }

    static void getOnPrefBetween(List<Query> qrs, int r, int x, int y, int id, int sign) {
        getOnPrefSmaller(qrs, r, y, id, sign);
        getOnPrefSmaller(qrs, r, x, id, -sign);
    }

    static void getOnSegmentBetween(List<Query> qrs, int l, int r, int x, int y, int id, int sign) {
        if (x > y) return;
        getOnPrefBetween(qrs, r, x, y, id, sign);
        getOnPrefBetween(qrs, l, x, y, id, -sign);
    }

    @Override
    public void run() {

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int q = in.nextInt();

        int[] l = new int[q];
        int[] r = new int[q];

        for (int i = 0; i < q; i++) {
            l[i] = in.nextInt() - 1;
            r[i] = in.nextInt() - 1;
        }

        int[] perm = new int[n];

        for (int i = 0; i < n; i++) {
            perm[i] = n - i - 1;
        }

        final int BLOCK = 300;

        long inv = 0L;

        boolean[] isInteresting = new boolean[n];

        long[] add = new long[q];

        Fenwick f = new Fenwick(n);

        for (int i = 0; i < q; i += BLOCK) {
            int from = i, to = Math.min(i + BLOCK, q) - 1;
            List<Integer> lst = new ArrayList<>();
            for (int j = from; j <= to; j++) {
                lst.add(l[j]);
                lst.add(r[j]);
            }
            lst.sort(Integer::compareTo);
            lst = new ArrayList<>(new HashSet<>(lst));
            int[] interestingPositions = lst.stream().mapToInt(x -> x).toArray();
            for (int pos : interestingPositions) {
                isInteresting[pos] = true;
            }
            List<Query> qrs = new ArrayList<>();
            for (int j = from; j <= to; j++) {
                if (l[j] == r[j]) continue;
                if (l[j] > r[j]) {
                    int tmp = l[j];
                    l[j] = r[j];
                    r[j] = tmp;
                }
                if (perm[l[j]] < perm[r[j]]) {
                    getOnSegmentBetween(qrs, l[j], r[j], perm[l[j]], perm[r[j]], j,-1);
                    int leftValue = perm[l[j]];
                    int rightValue = perm[r[j]];
                    for (int pos : interestingPositions) {
                        if (pos > l[j] && pos < r[j] && perm[pos] > leftValue && perm[pos] < rightValue) {
                            add[j] -= 2;
                        }
                    }
                    add[j]--;
                } else {
                    getOnSegmentBetween(qrs, l[j], r[j], perm[r[j]], perm[l[j]], j,1);
                    int leftValue = perm[l[j]];
                    int rightValue = perm[r[j]];
                    for (int pos : interestingPositions) {
                        if (pos > l[j] && pos < r[j] && perm[pos] > rightValue && perm[pos] < leftValue) {
                            add[j] += 2;
                        }
                    }
                    add[j]++;
                }
                int tmp = perm[l[j]];
                perm[l[j]] = perm[r[j]];
                perm[r[j]] = tmp;
            }
            qrs.sort(Comparator.comparingInt(a -> -a.x));

            f.clear();
            for (int pos = 0; pos < n; pos++) {
                if (!isInteresting[pos]) {
                    f.add(perm[pos], 1);
                }
                while (!qrs.isEmpty() && qrs.get(qrs.size() - 1).x == pos) {
                    Query t = qrs.get(qrs.size() - 1);
                    qrs.remove(qrs.size() - 1);
                    add[t.id] += 2 * t.sign * f.sum(t.bound);
                }
            }
            for (int j = from; j <= to; j++) {
                inv += add[j];
                out.println(inv);
            }
            for (int pos : interestingPositions) {
                isInteresting[pos] = false;
            }
        }



        out.close();
    }

    public static void main(String[] args) {
        new Thread(null, new NsqrtNlogNnetman(), "1", 1L << 28).run();
    }
}

#include <iostream>
#include <string>

using namespace std;

int main()
{
	int n; cin >> n;
	string s; cin >> s;
	int k_a = 0, k_d = 0;
	for (int i = 0; i < n; i++)
		if (s[i] == 'A') k_a++; else k_d++;
	if (k_a > k_d) cout << "Anton" << endl;
	if (k_a < k_d) cout << "Danik" << endl;
	if (k_a == k_d) cout << "Friendship" << endl;
	return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int k2, k3, k5, k6;
	cin >> k2 >> k3 >> k5 >> k6;
	int n256 = min(k2, min(k5, k6));
	int n32 = min(k3, k2 - n256);
	cout << 32 * n32 + 256 * n256 << endl;
	return 0;
}

#include <iostream>

using namespace std;

const int max_n = 1000000;

int n, m, k;
int x, s;
int a[max_n], b[max_n], c[max_n], d[max_n];

inline int max_complete(int money_left)
{
	int l = 0, r = k;
	while (l < r)
	{
		int m = (l + r + 1) / 2;
		if (d[m] <= money_left) l = m; else r = m-1;
	}
	return c[l];
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	cin >> x >> s;
	a[0] = x;
	b[0] = 0;
	c[0] = 0;
	d[0] = 0;
	for (int i = 1; i <= m; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];
	for (int i = 1; i <= k; i++) cin >> c[i];
	for (int i = 1; i <= k; i++) cin >> d[i];
	long long ans = 1LL * n * x;
	for (int i = 0; i <= m; i++)
	{
		int money_left = s - b[i];
		if (money_left < 0) continue;
		ans = min(ans, 1LL * (n - max_complete(money_left)) * a[i]);
	}
	cout << ans << endl;
	return 0;
}

#include <cstdio>
#include <algorithm>

using namespace std;

inline char in_char()
{
	char c = '\0';
	while (c <= ' ')
		c = getchar();
	return c;
}

inline int in_int()
{
	int n;
	scanf("%d", &n);
	return n;
}

struct figurine
{
	char kind;
	int x, y;
};

int n;
int x0, y0;
figurine nearest[8];

inline int dist(int x1, int y1, int x2, int y2)
{
	return max(abs(x1 - x2), abs(y1 - y2));
}

inline void upd_nearest(figurine& was, const figurine& cur)
{
	if (was.kind == '?' ||
	    dist(x0, y0, cur.x, cur.y) < dist(x0, y0, was.x, was.y))
	was = cur;
}

inline int get_direction(const figurine& cur)
{
	// vertical
	if (cur.x == x0 && cur.y < y0) return 0;
	if (cur.x == x0 && cur.y > y0) return 1;
	// horizontal
	if (cur.y == y0 && cur.x < x0) return 2;
	if (cur.y == y0 && cur.x > x0) return 3;
	// diagonal 1
	if ((cur.y - y0) == (cur.x - x0) && cur.x < x0) return 4;
	if ((cur.y - y0) == (cur.x - x0) && cur.x > x0) return 5;
	// diagonal 2
	if ((cur.y - y0) == (x0 - cur.x) && cur.y < y0) return 6;
	if ((cur.y - y0) == (x0 - cur.x) && cur.y > y0) return 7;
	// the piece doesn't lie on any of the eight directions
	return -1;
}

int main()
{
	n = in_int();
	x0 = in_int(); y0 = in_int();
	for (int i = 0; i < 8; i++)
		nearest[i].kind = '?';
	// read and update nearest
	for (int i = 0; i < n; i++)
	{
		figurine cur;
		cur.kind = in_char(); cur.x = in_int(); cur.y = in_int();
		int dir = get_direction(cur);
		if (dir >= 0)
			upd_nearest(nearest[dir], cur);
	}
	bool ans = false;
	// check verticals and horizontals
	for (int i = 0; i < 4; i++)
		if (nearest[i].kind == 'R' || nearest[i].kind == 'Q')
			ans = true;
	// check diagonals
	for (int i = 4; i < 8; i++)
		if (nearest[i].kind == 'B' || nearest[i].kind == 'Q')
			ans = true;
	// output
	puts(ans ? "YES" : "NO");
	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector <int> color;
vector < vector <int> > g;
vector <char> used;
vector <int> comp;
int n1;
vector < vector <int> > g1;
vector <int> dp;
int ans = 0;

void dfs1(int v, int col, int cmp)
{
    if (used[v]) return;
    if (color[v] != col) return;
    used[v] = true;
    comp[v] = cmp;
    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        dfs1(to, col, cmp);
    }
}

void dfs2(int v, int p = -1)
{
    int mx1 = 0, mx2 = 0;
    for (int i = 0; i < g1[v].size(); i++)
    {
        int to = g1[v][i];
        if (to == p) continue;
        dfs2(to, v);
        int val = dp[to] + 1;
        mx2 = max(mx2, val);
        if (mx1 < mx2) swap(mx1, mx2);
    }
    dp[v] = mx1;
    ans = max(ans, mx1 + mx2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    color.resize(n);
    g.resize(n);
    comp.resize(n);
    used.assign(n, false);
    for (int i = 0; i < n; i++) cin >> color[i];
    for (int i = 1; i < n; i++)
    {
        int a, b; cin >> a >> b; a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < n; i++)
        if (!used[i])
            dfs1(i, color[i], n1++);
    g1.resize(n1);
    dp.resize(n1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < g[i].size(); j++)
        {
            int to = g[i][j];
            if (comp[i] != comp[to])
                g1[comp[i]].push_back(comp[to]);
        }
    dfs2(0);
    cout << (ans + 1) / 2 << endl;
    return 0;
}

#include <iostream>

using namespace std;

const int max_n = 300000;

int n;
int b[max_n];
int c[max_n];
int a[max_n];
int d[max_n];
int b1[max_n];
int c1[max_n];
int bits[31][max_n];
int kbit[31];

int main()
{
	// input
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> b[i];
	for (int i = 0; i < n; i++) cin >> c[i];
	for (int i = 0; i < n; i++) d[i] = b[i] + c[i];

	// searching for answer
	long long sum = 0;
	for (int i = 0; i < n; i++) sum += d[i];
	sum /= (2 * n);

	for (int i = 0; i < n; i++) a[i] = (d[i] - sum) / n;

	// checking the answer
    for (int i = 0; i < n; i++)
        if (a[i] < 0)
        {
            cout << -1 << endl;
            return 0;
        }
	
	for (int i = 0; i < 31; i++)
		for (int j = 0; j < n; j++)
			if ((a[j] & (1LL << i)) == 0)
				bits[i][j] = 0;
			else
				bits[i][j] = 1;
	for (int i = 0; i < 31; i++)
	{
		kbit[i] = 0;
		for (int j = 0; j < n; j++)
			kbit[i] += bits[i][j];
	}

	for (int i = 0; i < n; i++) b1[i] = 0;
	for (int i = 0; i < n; i++) c1[i] = 0;

	for (int i = 0; i < 31; i++)
		for (int j = 0; j < n; j++)
		{
			int bbase = bits[i][j] ? kbit[i] : 0;
			int cbase = bits[i][j] ? n : kbit[i];
			b1[j] += bbase << i;
			c1[j] += cbase << i;
		} 

	for (int i = 0; i < n; i++)
		if (b1[i] != b[i] || c1[i] != c[i])
		{
			cout << -1 << endl;
			return 0;
		}	

	// output
	for (int i = 0; i < n; i++) cout << a[i] << " ";
	cout << endl;
	return 0;
}