結果
| 問題 |
No.838 Noelちゃんと星々3
|
| コンテスト | |
| ユーザー |
 バイト
|
| 提出日時 | 2019-06-19 14:32:18 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 60,062 bytes |
| コンパイル時間 | 3,748 ms |
| コンパイル使用メモリ | 239,856 KB |
| 実行使用メモリ | 25,908 KB |
| 最終ジャッジ日時 | 2024-11-30 08:01:21 |
| 合計ジャッジ時間 | 9,733 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 19 WA * 4 RE * 3 |
ソースコード
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace std::chrono;
#define int long long
#define ll long long
auto start_time = system_clock::now();
//@formatter:off
#ifdef _DEBUG
//区間削除は出来ない
template<class T> struct my_pbds_tree { set<T> s; auto begin() { return s.begin(); } auto end() { return s.end(); } auto rbegin() { return s.rbegin(); } auto rend() { return s.rend(); } auto empty() { return s.empty(); } auto size() { return s.size(); } void clear() { s.clear(); } template<class U> void insert(U v) { s.insert(v); } template<class U> void operator+=(U v) { insert(v); } template<class F> auto erase(F v) { return s.erase(v); } template<class U> auto find(U v) { return s.find(v); } template<class U> auto lower_bound(U v) { return s.lower_bound(v); } template<class U> auto upper_bound(U v) { return s.upper_bound(v); } auto find_by_order(int k) { auto it = s.begin(); for (int i = 0; i < k; i++)it++; return it; } auto order_by_key(int v) { auto it = s.begin(); int i=0; for (;it != s.end() && *it <v ; i++)it++; return i; }};
#define pbds(T) my_pbds_tree<T>
#else
#define unordered_map __gnu_pbds::gp_hash_table
//find_by_order(k) k番目のイテレーター
//order_of_key(k) k以上が前から何番目か
#define pbds(U) __gnu_pbds::tree<U, __gnu_pbds::null_type, less<U>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>
#endif
struct xorshift { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } size_t operator()(std::pair<ll, ll> x) const { int v=((x.first) << 32) | x.second; static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(v + FIXED_RANDOM); }};
template<class U, class L> void operator+=(__gnu_pbds::tree<U, __gnu_pbds::null_type, less<U>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> &s, L v) { s.insert(v); }
//衝突対策
#define ws wszzzz
template<class A, class B, class C>struct T2 {A f;B s;C t;T2() { f = 0, s = 0, t = 0; }T2(A f, B s, C t) : f(f), s(s), t(t) {}bool operator<(const T2 &r) const { return f != r.f ? f < r.f : s != r.s ? s < r.s : t < r.t; /*return f != r.f ? f > r.f : s != r.s ?n s > r.s : t > r.t; 大きい順 */ } bool operator>(const T2 &r) const { return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; /*return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 小さい順 */ } bool operator==(const T2 &r) const { return f == r.f && s == r.s && t == r.t; } bool operator!=(const T2 &r) const { return f != r.f || s != r.s || t != r.t; }};
template<class A, class B, class C, class D> struct F2 { A a; B b; C c; D d; F2() { a = 0, b = 0, c = 0, d = 0; } F2(A a, B b, C c, D d) : a(a), b(b), c(c), d(d) {} bool operator<(const F2 &r) const { return a != r.a ? a < r.a : b != r.b ? b < r.b : c != r.c ? c < r.c : d < r.d; /* return a != r.a ? a > r.a : b != r.b ? b > r.b : c != r.c ? c > r.c : d > r.d;*/ } bool operator>(const F2 &r) const { return a != r.a ? a > r.a : b != r.b ? b > r.b : c != r.c ? c > r.c : d > r.d;/* return a != r.a ? a < r.a : b != r.b ? b < r.b : c != r.c ? c < r.c : d < r.d;*/ } bool operator==(const F2 &r) const { return a == r.a && b == r.b && c == r.c && d == r.d; } bool operator!=(const F2 &r) const { return a != r.a || b != r.b || c != r.c || d != r.d; } int operator[](int i) { assert(i < 4); return i == 0 ? a : i == 1 ? b : i == 2 ? c : d; }};
typedef T2<int, int, int> T;
typedef F2<int, int, int, int> F;
T mt(int a, int b, int c) {return T(a, b, c);}
//@マクロ省略系 型,構造
#define double long double
#define ull unsigned long long
using dou = double;
using itn = int;
using str = string;
using bo= bool;
#define au auto
using P = pair<int, int>;
using pd =pair<dou, dou>;
#define fi first
#define se second
#define beg begin
#define rbeg rbegin
#define con continue
#define bre break
#define brk break
#define is ==
#define elf else if
#define wh while
#define maxq 1
#define minq -1
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MALLOC(type, len) (type*)malloc((len) * sizeof(type))
#define lam(right) [&](int& p){return p right;}
//マクロ省略系 コンテナ
using vi = vector<int>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vc = vector<char>;
using vp = vector<P>;
using vt = vector<T>;
#define V vector
#define o_vvt(o1, o2, o3, o4, name, ...) name
#define vvt0(t) V<V<t>>
#define vvt1(t,a) V<V<t>>a
#define vvt2(t,a, b) V<V<t>>a(b)
#define vvt3(t,a, b, c) V<V<t>> a(b,V<t>(c))
#define vvt4(t,a, b, c, d) V<V<t>> a(b,V<t>(c,d))
#define vvi(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(int,__VA_ARGS__)
#define vvb(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(bool,__VA_ARGS__)
#define vvs(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(string,__VA_ARGS__)
#define vvd(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(double,__VA_ARGS__)
#define vvc(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(char,__VA_ARGS__)
#define vvp(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(P,__VA_ARGS__)
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) {return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));}
#define vni(name, ...) auto name = make_v<int>(__VA_ARGS__)
#define vnb(name, ...) auto name = make_v<bool>(__VA_ARGS__)
#define vns(name, ...) auto name = make_v<string>(__VA_ARGS__)
#define vnd(name, ...) auto name = make_v<double>(__VA_ARGS__)
#define vnc(name, ...) auto name = make_v<char>(__VA_ARGS__)
#define vnp(name, ...) auto name = make_v<P>(__VA_ARGS__)
#define PQ priority_queue<int, vector<int>, greater<int> >
#define tos to_string
using mapi = map<int, int>;
using mapp = map<P, int>;
using mapd = map<dou, int>;
using mapc = map<char, int>;
using maps = map<str, int>;
using seti = set<int>;
using setd = set<dou>;
using setc = set<char>;
using sets = set<str>;
using qui = queue<int>;
#define bset bitset
#define uset unordered_set
#define useti unordered_set<int,int,xorshift>
#define mset multiset
#define umap unordered_map
#define umapi unordered_map<int,int,xorshift>
#define umapp unordered_map<P,int,xorshift>
#define mmap multimap
template<class T> struct pq { priority_queue<T, vector<T>, greater<T> > q;/*小さい順*/ T su = 0; void clear() {q = priority_queue<T, vector<T>, greater<T> >();su = 0;} void operator+=(T v) {su += v;q.push(v);} T sum() {return su;} T top() {return q.top();} void pop() {su -= q.top();q.pop();} T poll() {T ret = q.top();su -= ret;q.pop();return ret;} int size() {return q.size();}};
template<class T> struct pqg { priority_queue<T> q;/*大きい順*/ T su = 0; void clear() {q = priority_queue<T>();su = 0;} void operator+=(T v) {su += v;q.push(v);} T sum() {return su;} T top() {return q.top();} void pop() {su -= q.top();q.pop();} T poll() {T ret = q.top();su -= ret;q.pop();return ret;} int size() {return q.size();}};
#define pqi pq<int>
#define pqgi pqg<int>
//マクロ 繰り返し
#define o_rep(o1, o2, o3, o4, name, ...) name
# define rep1(n) for(int rep1i = 0,rep1lim=n; rep1i < rep1lim ; ++rep1i)
# define rep2(i, n) for(int i = 0,rep2lim=n; i < rep2lim ; ++i)
#define rep3(i, m, n) for(int i = m,rep3lim=n; i < rep3lim ; ++i)
#define rep4(i, m, n, ad) for(int i = m,rep4lim=n; i < rep4lim ; i+= ad)
#define rep(...) o_rep(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rer2(i, n) for(int i = n; i >= 0 ; i--)
#define rer3(i, m, n) for(int i = m,rer3lim=n; i >= rer3lim ; i--)
#define rer4(i, m, n, dec) for(int i = m,rer4lim=n; i >= rer4lim ; i-=dec)
#define rer(...) o_rep(__VA_ARGS__,rer4,rer3,rer2,)(__VA_ARGS__)
#define reps2(i, j, n) for(int i = 0,reps2lim=n; i < reps2lim ;++i)for(int j = 0; j < reps2lim ; ++j)
#define reps3(i, j, k, n) for(int i = 0,reps3lim=n; i < reps3lim ; ++i)for(int j = 0; j < reps3lim ; ++j)for(int k = 0; k < reps3lim ; ++k)
#define reps4(i, j, k, l, n) for(int i = 0,reps4lim=n; i < reps4lim ; ++i)for(int j = 0; j < reps4lim ; ++j)for(int k = 0; k < reps4lim ; ++k)for(int l = 0; l < reps4lim ; ++l)
#define o_reps(o1, o2, o3, o4, o5, name, ...) name
#define reps(...) o_reps(__VA_ARGS__,reps4,reps3,reps2,rep2,)(__VA_ARGS__)
#define repss(i, j, k, a, b, c) for(int i = 0; i < a ; ++i)for(int j = 0; j < b ; ++j)for(int k = 0; k < c ; ++k)
#define fora(a, b) for(auto&& a : b)
#define forg(gi, ve) for (int gi = 0,forglim = ve.size(), f, t, c; gi < forglim && (f = ve[gi].f, t = ve[gi].t, c = ve[gi].c, true); ++gi)
#define fort(gi, ve) for (int gi = 0, f, t, c; gi < ve.size() && (f = ve[gi].f, t = ve[gi].t, c = ve[gi].c, true); ++gi)if(t!=p)
#define form(st, l, r) for (auto &&it = st.lower_bound(l); it != st.end() && (*it).fi < r; ++it)
#define forit(st, l, r) for (auto &&it = st.lower_bound(l); it != st.end() && (*it) < r;)
//マクロ 定数
#define k3 1010
#define k4 10101
#define k5 101010
#define k6 1010101
#define k7 10101010
const int inf = (int) 1e9 + 100;
const ll linf = (ll) 1e18 + 100;
const char infc = '{';
const string infs = "{";
const double eps = 1e-9;
const double PI = 3.1415926535897932384626433832795029L;
ll ma = numeric_limits<ll>::min();
ll mi = numeric_limits<ll>::max();
//マクロ省略形 関数等
#define arsz(a) (sizeof(a)/sizeof(a[0]))
#define sz(a) ((int)(a).size())
#define mp make_pair
#define pb pop_back
#define pf push_front
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
constexpr bool ev(int a) { return !(a & 1); }
constexpr bool od(int a) { return (a & 1); }
//@拡張系 こう出来るべきというもの
//埋め込み 存在を意識せずに機能を増やされているもの
//@formatter:on
namespace std {
template<> class hash<std::pair<signed, signed>> { public:size_t operator()(const std::pair<signed, signed> &x) const { return hash<ll>()(((ll) x.first << 32) | x.second); }};
template<> class hash<std::pair<ll, ll>> { public:/*大きいllが渡されると、<<32でオーバーフローするがとりあえず問題ないと判断*/size_t operator()(const std::pair<ll, ll> &x) const { return hash<ll>()(((ll) x.first << 32) | x.second); }};
}
//@formatter:off
//stream まとめ
istream &operator>>(istream &iss, P &a) {iss >> a.first >> a.second;return iss;}template<typename T> istream &operator>>(istream &iss, vector<T> &vec) {for (T &x: vec) iss >> x;return iss;}template<class T, class U> ostream &operator<<(ostream &os, pair<T, U> p) {os << p.fi << " " << p.se << endl;return os;}ostream &operator<<(ostream &os, T p) { os << p.f << " " << p.s << " " << p.t; return os;}ostream &operator<<(ostream &os, F p) { os << p.a << " " << p.b << " " << p.c << " " << p.d; return os;}template<typename T> ostream &operator<<(ostream &os, vector <T> &vec) { for (int i = 0; i < vec.size(); ++i)os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os;}template<typename T> ostream &operator<<(ostream &os, vector <vector<T>> &vec) { for (int i = 0; i < vec.size(); ++i) { for (int j = 0; j < vec[0].size(); ++j) { os << vec[i][j]; } os << endl; } return os;}template<typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &m) { for (auto &&v:m) os << v; return os;}
template<typename W, typename H> void resize(vector<W> &vec, const H head) { vec.resize(head); }template<typename W, typename H, typename ... T> void resize(vector<W> &vec, const H &head, const T ... tail) {vec.resize(head);for (auto &v: vec)resize(v, tail...);}
template<typename T, typename F> bool all_of2(T &v, F f) { return f(v); }
template<typename T, typename F> bool all_of2(vector<T> &v, F f) { rep(i, sz(v)) { if (!all_of2(v[i], f))return false; } return true;}
template<typename T, typename F> bool any_of2(T &v, F f) { return f(v); }
template<typename T, typename F> bool any_of2(vector<T> &v, F f) { rep(i, sz(v)) { if (any_of2(v[i], f))return true; } return false;}
template<typename T, typename F> bool none_of2(T &v, F f) { return f(v); }
template<typename T, typename F> bool none_of2(vector<T> &v, F f) { rep(i, sz(v)) { if (none_of2(v[i], f))return false; } return true;}
template<typename T, typename F> bool find_if2(T &v, F f) { return f(v); }
template<typename T, typename F> int find_if2(vector<T> &v, F f) { rep(i, sz(v)) { if (find_if2(v[i], f))return i; } return sz(v);}
template<typename T, typename F> bool rfind_if2(T &v, F f) { return f(v); }
template<typename T, typename F> int rfind_if2(vector<T> &v, F f) { rer(i, sz(v) - 1) { if (rfind_if2(v[i], f))return i; } return -1;}
template<class T> bool contains(string &s, const T &v) { return s.find(v) != string::npos; }
template<typename T> bool contains(vector<T> &v, const T &val) { return std::find(v.begin(), v.end(), val) != v.end(); }
template<typename T, typename F> bool contains_if2(vector<T> &v, F f) { return find_if(v.begin(), v.end(), f) != v.end(); }
template<typename T, typename F> int count_if2(T &v, F f) { return f(v); }
template<typename T, typename F> int count_if2(vector<T> &vec, F f) { int ret = 0; fora(v, vec)ret += count_if2(v, f); return ret;}
template<typename T, typename F> void for_each2(T &v, F f) { f(v); }
template<typename T, typename F> void for_each2(vector<T> &vec, F f) { fora(v, vec)for_each2(v, f); }
template<typename W> int count_od(vector<W> &a) {return count_if2(a,[](int v){return v&1 ;});}
template<typename W> int count_ev(vector<W> &a) {return count_if2(a,[](int v){return !(v&1) ;});}
#define all_of(a,right) all_of2(a,lam(right))
#define any_of(a,right) any_of2(a,lam(right))
#define none_of(a,right) none_of2(a,lam(right))
#define find_if(a,right) find_if2(a,lam(right))
#define rfind_if(a,right) rfind_if2(a,lam(right))
#define contains_if(a,right) contains_if2(a,lam(right))
#define count_if(a, right) count_if2(a,lam(right))
#define for_each(a, right) do{fora(v,a){v right;}}while(0)
template<class T, class U> void replace(vector<T> &a, T key, U v) { replace(a.begin(), a.end(), key, v); }
void replace(str &a, char key, str v) { if (v == "")a.erase(remove(all(a), key), a.end()); }
void replace(str &a, char key, char v) { replace(all(a), key, v); }
//keyと同じかどうか01で置き換える
template<class T, class U> void replace(vector<T> &a, U k) { rep(i, sz(a)) a[i] = a[i] == k; }
template<class T, class U> void replace(vector<vector<T >> &a, U k) { rep(i, sz(a))rep(j, sz(a[0])) a[i][j] = a[i][j] == k; }
template<class T> void replace(T &a) { replace(a, '#'); }
void replace(str &a, str key, str v) {stringstream t;int kn = sz(key);std::string::size_type Pos(a.find(key));int l = 0;while (Pos != std::string::npos) {t << a.substr(l, Pos - l);t << v;l = Pos + kn;Pos = a.find(key, Pos + kn);}t << a.substr(l, sz(a) - l);a = t.str();}
template<class T> bool includes(vector<T> &a, vector<T> &b) {vi c = a;vi d = b;sort(all(c));sort(all(d));return includes(all(c), all(d));}
template<class T> bool is_permutation(vector<T> &a, vector<T> &b) { return is_permutation(all(a), all(b)); }
template<class T> bool next_permutation(vector<T> &a) { return next_permutation(all(a)); }
void iota(vector<int> &ve, int s, int n) {ve.resize(n);iota(all(ve), s);}
vi iota(int s, int len) {vi ve(len);iota(all(ve), s);return ve;}
template<class A, class B> auto vtop(vector<A> &a, vector<B> &b) { assert(sz(a) == sz(b)); /*stringを0で初期化できない */ vector<pair<A, B>> res; rep(i, sz(a))res.eb(a[i], b[i]);return res;}
template<class A, class B> void ptov(vector<pair<A, B>> &p, vector<A> &a, vector<B> &b) { a.resize(sz(p)), b.resize(sz(p)); rep(i, sz(p))a[i] = p[i].fi, b[i] = p[i].se;}
template<class A, class B, class C> auto vtot(vector<A> &a, vector<B> &b, vector<C> &c) { assert(sz(a) == sz(b) && sz(b) == sz(c)); vector<T2<A, B, C>> res; rep(i, sz(a))res.eb(a[i], b[i], c[i]); return res;}
template<class A, class B, class C, class D> auto vtof(vector<A> &a, vector<B> &b, vector<C> &c, vector<D> &d) { assert(sz(a) == sz(b) && sz(b) == sz(c) && sz(c) == sz(d)); vector<F2<A, B, C, D>> res; rep(i, sz(a))res.eb(a[i], b[i], c[i], d[i]); return res;}
enum pcomparator { fisi, fisd, fdsi, fdsd, sifi, sifd, sdfi, sdfd };
enum tcomparator { fisiti, fisitd, fisdti, fisdtd, fdsiti, fdsitd, fdsdti, fdsdtd, fitisi, fitisd, fitdsi, fitdsd, fdtisi, fdtisd, fdtdsi, fdtdsd, sifiti, sifitd, sifdti, sifdtd, sdfiti, sdfitd, sdfdti, sdfdtd, sitifi, sitifd, sitdfi, sitdfd, sdtifi, sdtifd, sdtdfi, sdfdfd, tifisi, tifisd, tifdsi, tifdsd, tdfisi, tdfisd, tdfdsi, tdfdsd, tisifi, tisifd, tisdfi, tisdfd, tdsifi, tdsifd, tdsdfi, tdsdfd};
template<class A, class B> void sort(vector<pair<A, B>> &a, pcomparator type) { typedef pair<A, B> U; if (type == fisi) sort(all(a), [&](U l, U r) { return l.fi != r.fi ? l.fi < r.fi : l.se < r.se; }); else if (type == fisd) sort(all(a), [&](U l, U r) { return l.fi != r.fi ? l.fi < r.fi : l.se > r.se; }); else if (type == fdsi) sort(all(a), [&](U l, U r) { return l.fi != r.fi ? l.fi > r.fi : l.se < r.se; }); else if (type == fdsd) sort(all(a), [&](U l, U r) { return l.fi != r.fi ? l.fi > r.fi : l.se > r.se; }); else if (type == sifi) sort(all(a), [&](U l, U r) { return l.se != r.se ? l.se < r.se : l.fi < r.fi; }); else if (type == sifd) sort(all(a), [&](U l, U r) { return l.se != r.se ? l.se < r.se : l.fi > r.fi; }); else if (type == sdfi) sort(all(a), [&](U l, U r) { return l.se != r.se ? l.se > r.se : l.fi < r.fi; }); else if (type == sdfd) sort(all(a), [&](U l, U r) { return l.se != r.se ? l.se > r.se : l.fi > r.fi; });};template<class U> void sort(vector<U> &a, pcomparator type) { if (type == fisi) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s < r.s; }); else if (type == fisd) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s > r.s; }); else if (type == fdsi) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s < r.s; }); else if (type == fdsd) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s > r.s; }); else if (type == sifi) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f < r.f; }); else if (type == sifd) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f > r.f; }); else if (type == sdfi) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f < r.f; }); else if (type == sdfd) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f > r.f; });};template<class A, class B, class C, class D> void sort(vector<F2<A, B, C, D> > &a, pcomparator type) { typedef F2<A, B, C, D> U; if (type == fisi) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b < r.b; }); else if (type == fisd) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b > r.b; }); else if (type == fdsi) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b < r.b; }); else if (type == fdsd) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b > r.b; }); else if (type == sifi) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a < r.a; }); else if (type == sifd) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a > r.a; }); else if (type == sdfi) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a < r.a; }); else if (type == sdfd) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a > r.a; });};template<class U> void sort(vector<U> &a, tcomparator type) { if (type == 0) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s != r.s ? l.s < r.s : l.t < r.t; }); else if (type == 1) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s != r.s ? l.s < r.s : l.t > r.t; }); else if (type == 2) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s != r.s ? l.s > r.s : l.t < r.t; }); else if (type == 3) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s != r.s ? l.s > r.s : l.t > r.t; }); else if (type == 4) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s != r.s ? l.s < r.s : l.t < r.t; }); else if (type == 5) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s != r.s ? l.s < r.s : l.t > r.t; }); else if (type == 6) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s != r.s ? l.s > r.s : l.t < r.t; }); else if (type == 7) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s != r.s ? l.s > r.s : l.t > r.t; }); else if (type == 8) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.t != r.t ? l.t < r.t : l.s < r.s; }); else if (type == 9) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.t != r.t ? l.t < r.t : l.s > r.s; }); else if (type == 10) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.t != r.t ? l.t > r.t : l.s < r.s; }); else if (type == 11) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.t != r.t ? l.t > r.t : l.s > r.s; }); else if (type == 12) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.t != r.t ? l.t < r.t : l.s < r.s; }); else if (type == 13) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.t != r.t ? l.t < r.t : l.s > r.s; }); else if (type == 14) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.t != r.t ? l.t > r.t : l.s < r.s; }); else if (type == 15) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.t != r.t ? l.t > r.t : l.s > r.s; }); else if (type == 16) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f != r.f ? l.f < r.f : l.t < r.t; }); else if (type == 17) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f != r.f ? l.f < r.f : l.t > r.t; }); else if (type == 18) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f != r.f ? l.f > r.f : l.t < r.t; }); else if (type == 19) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f != r.f ? l.f > r.f : l.t > r.t; }); else if (type == 20) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f != r.f ? l.f < r.f : l.t < r.t; }); else if (type == 21) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f != r.f ? l.f < r.f : l.t > r.t; }); else if (type == 22) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f != r.f ? l.f > r.f : l.t < r.t; }); else if (type == 23) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f != r.f ? l.f > r.f : l.t > r.t; }); else if (type == 24) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.t != r.t ? l.t < r.t : l.f < r.f; }); else if (type == 25) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.t != r.t ? l.t < r.t : l.f > r.f; }); else if (type == 26) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.t != r.t ? l.t > r.t : l.f < r.f; }); else if (type == 27) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.t != r.t ? l.t > r.t : l.f > r.f; }); else if (type == 28) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.t != r.t ? l.t < r.t : l.f < r.f; }); else if (type == 29) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.t != r.t ? l.t < r.t : l.f > r.f; }); else if (type == 30) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.t != r.t ? l.t > r.t : l.f < r.f; }); else if (type == 31) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.t != r.t ? l.t > r.t : l.f > r.f; }); else if (type == 32) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.f != r.f ? l.f < r.f : l.s < r.s; }); else if (type == 33) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.f != r.f ? l.f < r.f : l.s > r.s; }); else if (type == 34) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.f != r.f ? l.f > r.f : l.s < r.s; }); else if (type == 35) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.f != r.f ? l.f > r.f : l.s > r.s; }); else if (type == 36) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.f != r.f ? l.f < r.f : l.s < r.s; }); else if (type == 37) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.f != r.f ? l.f < r.f : l.s > r.s; }); else if (type == 38) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.f != r.f ? l.f > r.f : l.s < r.s; }); else if (type == 39) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.f != r.f ? l.f > r.f : l.s > r.s; }); else if (type == 40) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.s != r.s ? l.s < r.s : l.f < r.f; }); else if (type == 41) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.s != r.s ? l.s < r.s : l.f > r.f; }); else if (type == 42) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.s != r.s ? l.s > r.s : l.f < r.f; }); else if (type == 43) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.s != r.s ? l.s > r.s : l.f > r.f; }); else if (type == 44) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.s != r.s ? l.s < r.s : l.f < r.f; }); else if (type == 45) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.s != r.s ? l.s < r.s : l.f > r.f; }); else if (type == 46) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.s != r.s ? l.s > r.s : l.f < r.f; }); else if (type == 47) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.s != r.s ? l.s > r.s : l.f > r.f; });}template<class A, class B, class C, class D> void sort(vector<F2<A, B, C, D>> &a, tcomparator type) { typedef F2<A, B, C, D> U; if (type == 0) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b != r.b ? l.b < r.b : l.c < r.c; }); else if (type == 1) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b != r.b ? l.b < r.b : l.c > r.c; }); else if (type == 2) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b != r.b ? l.b > r.b : l.c < r.c; }); else if (type == 3) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b != r.b ? l.b > r.b : l.c > r.c; }); else if (type == 4) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b != r.b ? l.b < r.b : l.c < r.c; }); else if (type == 5) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b != r.b ? l.b < r.b : l.c > r.c; }); else if (type == 6) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b != r.b ? l.b > r.b : l.c < r.c; }); else if (type == 7) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b != r.b ? l.b > r.b : l.c > r.c; }); else if (type == 8) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.c != r.c ? l.c < r.c : l.b < r.b; }); else if (type == 9) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.c != r.c ? l.c < r.c : l.b > r.b; }); else if (type == 10) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.c != r.c ? l.c > r.c : l.b < r.b; }); else if (type == 11) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.c != r.c ? l.c > r.c : l.b > r.b; }); else if (type == 12) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.c != r.c ? l.c < r.c : l.b < r.b; }); else if (type == 13) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.c != r.c ? l.c < r.c : l.b > r.b; }); else if (type == 14) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.c != r.c ? l.c > r.c : l.b < r.b; }); else if (type == 15) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.c != r.c ? l.c > r.c : l.b > r.b; }); else if (type == 16) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a != r.a ? l.a < r.a : l.c < r.c; }); else if (type == 17) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a != r.a ? l.a < r.a : l.c > r.c; }); else if (type == 18) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a != r.a ? l.a > r.a : l.c < r.c; }); else if (type == 19) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a != r.a ? l.a > r.a : l.c > r.c; }); else if (type == 20) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a != r.a ? l.a < r.a : l.c < r.c; }); else if (type == 21) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a != r.a ? l.a < r.a : l.c > r.c; }); else if (type == 22) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a != r.a ? l.a > r.a : l.c < r.c; }); else if (type == 23) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a != r.a ? l.a > r.a : l.c > r.c; }); else if (type == 24) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.c != r.c ? l.c < r.c : l.a < r.a; }); else if (type == 25) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.c != r.c ? l.c < r.c : l.a > r.a; }); else if (type == 26) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.c != r.c ? l.c > r.c : l.a < r.a; }); else if (type == 27) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.c != r.c ? l.c > r.c : l.a > r.a; }); else if (type == 28) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.c != r.c ? l.c < r.c : l.a < r.a; }); else if (type == 29) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.c != r.c ? l.c < r.c : l.a > r.a; }); else if (type == 30) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.c != r.c ? l.c > r.c : l.a < r.a; }); else if (type == 31) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.c != r.c ? l.c > r.c : l.a > r.a; }); else if (type == 32) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.a != r.a ? l.a < r.a : l.b < r.b; }); else if (type == 33) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.a != r.a ? l.a < r.a : l.b > r.b; }); else if (type == 34) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.a != r.a ? l.a > r.a : l.b < r.b; }); else if (type == 35) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.a != r.a ? l.a > r.a : l.b > r.b; }); else if (type == 36) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.a != r.a ? l.a < r.a : l.b < r.b; }); else if (type == 37) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.a != r.a ? l.a < r.a : l.b > r.b; }); else if (type == 38) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.a != r.a ? l.a > r.a : l.b < r.b; }); else if (type == 39) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.a != r.a ? l.a > r.a : l.b > r.b; }); else if (type == 40) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.b != r.b ? l.b < r.b : l.a < r.a; }); else if (type == 41) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.b != r.b ? l.b < r.b : l.a > r.a; }); else if (type == 42) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.b != r.b ? l.b > r.b : l.a < r.a; }); else if (type == 43) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.b != r.b ? l.b > r.b : l.a > r.a; }); else if (type == 44) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.b != r.b ? l.b < r.b : l.a < r.a; }); else if (type == 45) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.b != r.b ? l.b < r.b : l.a > r.a; }); else if (type == 46) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.b != r.b ? l.b > r.b : l.a < r.a; }); else if (type == 47) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.b != r.b ? l.b > r.b : l.a > r.a; });}
void sort(string &a) { sort(all(a)); }
template<class T> void sort(vector<T> &a) { sort(all(a)); }
//P l, P rで f(P) の形で渡す
template<class U, class F> void sort(vector<U> &a, F f) { sort(all(a), [&](U l, U r) { return f(l) < f(r); }); };
template<class T> void rsort(vector<T> &a) { sort(all(a), greater<T>()); };
template<class U, class F> void rsort(vector<U> &a, F f) { sort(all(a), [&](U l, U r) { return f(l) > f(r); }); };
//F = T<T>
//例えばreturn p.fi + p.se;
template<class A, class B> void sortp(vector<A> &a, vector<B> &b) { auto c = vtop(a, b); sort(c); rep(i, sz(a)) a[i] = c[i].fi, b[i] = c[i].se;}template<class A, class B, class F> void sortp(vector<A> &a, vector<B> &b, F f) { auto c = vtop(a, b); sort(c, f); rep(i, sz(a)) a[i] = c[i].fi, b[i] = c[i].se;}template<class A, class B> void rsortp(vector<A> &a, vector<B> &b) { auto c = vtop(a, b); rsort(c); rep(i, sz(a))a[i] = c[i].first, b[i] = c[i].second;}template<class A, class B, class F> void rsortp(vector<A> &a, vector<B> &b, F f) { auto c = vtop(a, b); rsort(c, f); rep(i, sz(a))a[i] = c[i].first, b[i] = c[i].second;}
template<class A, class B, class C> void sortt(vector<A> &a, vector<B> &b, vector<C> &c) { auto d = vtot(a, b, c); sort(d); rep(i, sz(a)) a[i] = d[i].f, b[i] = d[i].s, c[i] = d[i].t;}
template<class A, class B, class C, class F> void sortt(vector<A> &a, vector<B> &b, vector<C> &c, F f) { auto d = vtot(a, b, c); sort(d, f); rep(i, sz(a)) a[i] = d[i].f, b[i] = d[i].s, c[i] = d[i].t;}
template<class A, class B, class C> void rsortt(vector<A> &a, vector<B> &b, vector<C> &c) { auto d = vtot(a, b, c); rsort(d); rep(i, sz(a)) a[i] = d[i].f, b[i] = d[i].s, c[i] = d[i].t;}
template<class A, class B, class C, class F> void rsortt(vector<A> &a, vector<B> &b, vector<C> &c, F f) { auto d = vtot(a, b, c); rsort(d, f); rep(i, sz(a)) a[i] = d[i].f, b[i] = d[i].s, c[i] = d[i].t;}
template<class A, class B, class C, class D> void sortf(vector<A> &a, vector<B> &b, vector<C> &c, vector<D> &d) { auto e = vtof(a, b, c, d); sort(e); rep(i, sz(a)) a[i] = e[i].a, b[i] = e[i].b, c[i] = e[i].c, d[i] = e[i].d;}
template<class A, class B, class C, class D> void rsortf(vector<A> &a, vector<B> &b, vector<C> &c, vector<D> &d) { auto e = vtof(a, b, c, d); rsort(e); rep(i, sz(a)) a[i] = e[i].a, b[i] = e[i].b, c[i] = e[i].c, d[i] = e[i].d;}
//sortindex 元のvectorはソートしない
template<class T> vi sorti(vector<T> &a) { auto b = a; vi ind = iota(0, sz(a)); sortp(b, ind); return ind;}/*indexの分で型が変わるためpcomparatorが必要*/template<class T> vi sorti(vector<T> &a, pcomparator f) { auto b = a; vi ind = iota(0, sz(a)); sortp(b, ind, f); return ind;}template<class T, class F> vi sorti(vector<T> &a, F f) { vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(a[x]) < f(a[y]); }); return ind;}template<class T> vi rsorti(vector<T> &a) { auto b = a; vi ind = iota(0, sz(a)); rsortp(b, ind); return ind;}template<class T, class F> vi rsorti(vector<T> &a, F f) { vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(a[x]) > f(a[y]); }); return ind;}template<class A, class B, class F> vi sortpi(vector<A> &a, vector<B> &b, F f) { auto c = vtop(a, b); vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(c[x]) < f(c[y]); }); return ind;}template<class A, class B> vi sortpi(vector<A> &a, vector<B> &b, pcomparator f) { vi ind = iota(0, sz(a)); auto c = a; auto d = b; sortt(c, d, ind, f); return ind;}template<class A, class B> vi sortpi(vector<A> &a, vector<B> &b) { return sortpi(a, b, fisi); };template<class A, class B, class F> vi rsortpi(vector<A> &a, vector<B> &b, F f) { auto c = vtop(a, b); vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(c[x]) > f(c[y]); }); return ind;}template<class A, class B> vi rsortpi(vector<A> &a, vector<B> &b) { return sortpi(a, b, fdsd); };template<class A, class B, class C, class F> vi sortti(vector<A> &a, vector<B> &b, vector<C> &c, F f) { auto d = vtot(a, b, c); vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(d[x]) < f(d[y]); }); return ind;}template<class A, class B, class C> vi sortti(vector<A> &a, vector<B> &b, vector<C> &c, pcomparator f) { vi ind = iota(0, sz(a)); auto d = vtof(a, b, c, ind); sort(d, f); rep(i, sz(a))ind[i] = d[i].d; return ind;}template<class A, class B, class C> vi sortti(vector<A> &a, vector<B> &b, vector<C> &c) { vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { if (a[x] == a[y]) { if (b[x] == b[y])return c[x] < c[y]; else return b[x] < b[y]; } else { return a[x] < a[y]; } }); return ind;}template<class A, class B, class C, class F> vi rsortti(vector<A> &a, vector<B> &b, vector<C> &c, F f) { auto d = vtot(a, b, c); vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(d[x]) > f(d[y]); }); return ind;}template<class A, class B, class C> vi rsortti(vector<A> &a, vector<B> &b, vector<C> &c) { vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { if (a[x] == a[y]) { if (b[x] == b[y])return c[x] > c[y]; else return b[x] > b[y]; } else { return a[x] > a[y]; } }); return ind;}
template<class T> void sort2(vector<vector<T >> &a) { for (int i = 0, n = a.size(); i < n; ++i)sort(a[i]); }
template<class T> void rsort2(vector<vector<T >> &a) { for (int i = 0, n = a.size(); i < n; ++i)rsort(a[i]); }
template<typename A, size_t N, typename T> void fill(A (&a)[N], const T &v) { rep(i, N)a[i] = v; }template<typename A, size_t N, size_t O, typename T> void fill(A (&a)[N][O], const T &v) { rep(i, N)rep(j, O)a[i][j] = v; }template<typename A, size_t N, size_t O, size_t P, typename T> void fill(A (&a)[N][O][P], const T &v) { rep(i, N)rep(j, O)rep(k, P)a[i][j][k] = v; }template<typename A, size_t N, size_t O, size_t P, size_t Q, typename T> void fill(A (&a)[N][O][P][Q], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)a[i][j][k][l] = v; }template<typename A, size_t N, size_t O, size_t P, size_t Q, size_t R, typename T> void fill(A (&a)[N][O][P][Q][R], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)a[i][j][k][l][m] = v; }template<typename A, size_t N, size_t O, size_t P, size_t Q, size_t R, size_t S, typename T> void fill(A (&a)[N][O][P][Q][R][S], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)rep(n, S)a[i][j][k][l][m][n] = v; }
template<typename W, typename T>void fill(W &xx, const T vall) { xx = vall;}template<typename W, typename T>void fill(vector<W> &vecc, const T vall) { for (auto &&vx : vecc)fill(vx, vall);}
template<class T,class U>void fill(vector<T> &a,U val,vi& ind) {fora(v,ind)a[v]=val;}
template<typename A, size_t N> A sum(A (&a)[N]) { A res = 0; rep(i, N)res += a[i]; return res;}template<typename A, size_t N, size_t O> A sum(A (&a)[N][O]) { A res = 0; rep(i, N)rep(j, O)res += a[i][j]; return res;}template<typename A, size_t N, size_t O, size_t P> A sum(A (&a)[N][O][P]) { A res = 0; rep(i, N)rep(j, O)rep(k, P)res += a[i][j][k]; return res;}template<typename A, size_t N, size_t O, size_t P, size_t Q> A sum(A (&a)[N][O][P][Q]) { A res = 0; rep(i, N)rep(j, O)rep(k, P)rep(l, Q)res += a[i][j][k][l]; return res;}template<typename A, size_t N, size_t O, size_t P, size_t Q, size_t R> A sum(A (&a)[N][O][P][Q][R]) { A res = 0; rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)res += a[i][j][k][l][m]; return res;}template<typename A, size_t N, size_t O, size_t P, size_t Q, size_t R, size_t S> A sum(A (&a)[N][O][P][Q][R][S]) { A res = 0; rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)rep(n, S)res += a[i][j][k][l][m][n]; return res;}
//@汎用便利関数 入力
int in() {int ret;cin >> ret;return ret;}
string sin() {string ret;cin >> ret;return ret;}
template<class T> void in(T &head) { cin >> head; }template<class T, class... U> void in(T &head, U &... tail) {cin >> head;in(tail...);}
#define o_din(o1, o2, o3, o4, name, ...) name
#define din1(a) int a;cin>>a
#define din2(a, b) int a,b;cin>>a>> b
#define din3(a, b, c) int a,b,c;cin>>a>>b>>c
#define din4(a, b, c, d) int a,b,c,d;cin>>a>>b>>c>>d
#define din(...) o_din(__VA_ARGS__,din4,din3,din2 ,din1)(__VA_ARGS__)
#define o_dind(o1, o2, o3, o4, name, ...) name
#define din1d(a) din1(a);a--
#define din2d(a, b) din2(a,b);a--,b--
#define din3d(a, b, c) din3(a,b,c);a--,b--,c--
#define din4d(a, b, c, d) din4(a,b,c,d);a--,b--,c--,d--
#define dind(...) o_dind(__VA_ARGS__,din4d,din3d,din2d ,din1d)(__VA_ARGS__)
#define o_out(o1, o2, o3, o4, name, ...) name
#define out1(a) cout<<a<<endl
#define out2(a, b) cout<<a<<" "<< b<<endl
#define out3(a, b, c) cout<<a<<" "<<b<<" "<<c<<endl
#define out4(a, b, c, d) cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl
#define out(...) o_out((__VA_ARGS__),out4,out3,out2,out1)((__VA_ARGS__))
template<class T>void outv(vector<T> &a,int W){ rep(i,W){ cout <<a[i]<< " "; } cout << "" << endl;}template<class T>void outv(vector<vector<T> > &a,int H,int W){ rep(h, H) { rep(w, W) { cout << a[h][w] << " "; } cout << "" << endl; }}
template<class T> void outl(vector<T> &a) { fora(v, a)cout << v << endl; }
template<class T> void na(vector<T> &a, int n) {a.resize(n);rep(i, n)cin >> a[i];}
#define dna(a, n) vi a(n); rep(dnai,n) cin >> a[dnai];
template<class T> void nao(vector<T> &a, int n) { a.resize(n + 1); a[0] = 0; rep(i, n)cin >> a[i + 1];}
template<class T> void naod(vector<T> &a, int n) { a.resize(n + 1); a[0] = 0; rep(i, n)cin >> a[i + 1],a[i+1]--;}
template<class T> void nad(vector<T> &a, int n) { a.resize(n); rep(i, n)cin >> a[i], a[i]--;}
template<class T, class U> void na2(vector<T> &a, vector<U> &b, int n) { a.resize(n); b.resize(n); rep(i, n)cin >> a[i] >> b[i];}
#define dna2(a, b, n) vi a(n),b(n);rep(dna2i, n)cin >> a[dna2i] >> b[dna2i];
template<class T, class U> void nao2(vector<T> &a, vector<U> &b, int n) { a.resize(n + 1); b.resize(n + 1); a[0] = b[0] = 0; rep(i, n)cin >> a[i + 1] >> b[i + 1];}
#define dna2d(a, b, n) vi a(n),b(n);rep(dna2di, n){cin >> a[dna2di] >> b[dna2di];a[dna2di]--,b[dna2di]--;}
template<class T, class U> void na2d(vector<T> &a, vector<U> &b, int n) { a.resize(n); b.resize(n); rep(i, n)cin >> a[i] >> b[i], a[i]--, b[i]--;}
template<class T, class U, class W> void na3(vector<T> &a, vector<U> &b, vector<W> &c, int n) { a.resize(n); b.resize(n); c.resize(n); rep(i, n)cin >> a[i] >> b[i] >> c[i];}
#define dna3(a, b, c, n) vi a(n),b(n),c(n); rep(dna3i, n)cin >> a[dna3i] >> b[dna3i] >> c[dna3i];
template<class T, class U, class W> void na3d(vector<T> &a, vector<U> &b, vector<W> &c, int n) { a.resize(n); b.resize(n); c.resize(n); rep(i, n)cin >> a[i] >> b[i] >> c[i], a[i]--, b[i]--, c[i]--;}
#define dna3d(a, b, c, n) vi a(n),b(n),c(n); rep(dna3di, n){cin >> a[dna3di] >> b[dna3di] >> c[dna3di];a[dna3di]--,b[dna3di]--,c[dna3di]--;}
#define nt(a, h, w) resize(a,h,w);rep(nthi,h)rep(ntwi,w) cin >> a[nthi][ntwi];
#define ntd(a, h, w) resize(a,h,w);rep(ntdhi,h)rep(ntdwi,w) cin >> a[ntdhi][ntdwi], a[ntdhi][ntdwi]--;
#define ntp(a, h, w) resize(a,h+2,w+2);fill(a,'#');rep(ntphi,1,h+1)rep(ntpwi,1,w+1) cin >> a[ntphi][ntpwi];
//デバッグ
#define sp << " " <<
#define debugName(VariableName) # VariableName
#define deb1(x) debugName(x)<<" = "<<x
#define deb2(x, ...) deb1(x) <<", "<< deb1(__VA_ARGS__)
#define deb3(x, ...) deb1(x) <<", "<< deb2(__VA_ARGS__)
#define deb4(x, ...) deb1(x) <<", "<< deb3(__VA_ARGS__)
#define deb5(x, ...) deb1(x) <<", "<< deb4(__VA_ARGS__)
#define deb6(x, ...) deb1(x) <<", "<< deb5(__VA_ARGS__)
#define deb7(x, ...) deb1(x) <<", "<< deb6(__VA_ARGS__)
#define deb8(x, ...) deb1(x) <<", "<< deb7(__VA_ARGS__)
#define deb9(x, ...) deb1(x) <<", "<< deb8(__VA_ARGS__)
#define deb10(x, ...) deb1(x) <<", "<< deb9(__VA_ARGS__)
#define o_ebug(o1, o2, o3, o4, o5, o6, o7, o8, o9, o10, name, ...) name
#ifdef _DEBUG
#define deb(...) cerr<< o_ebug(__VA_ARGS__,deb10,deb9,deb8,deb7,deb6,deb5,deb4,deb3,deb2,deb1)(__VA_ARGS__) <<endl
#else
#define deb(...) ;
#endif
#define debugline(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n'
//@formatter:on
//よく使うクラス、構造体
struct unionfind {
vector<int> par;
vector<int> siz;
vector<int> es;
int n, trees;//連結グループの数(親の種類)
unionfind(int n) : n(n), trees(n) {
par.resize(n);
siz.resize(n);
es.resize(n);
for (int i = 0; i < n; i++) {
par[i] = i;
siz[i] = 1;
}
}
int root(int x) { if (par[x] == x) { return x; } else { return par[x] = root(par[x]); }}
void unite(int x, int y) {
x = root(x);
y = root(y);
es[x]++;
if (x == y) return;
if (siz[x] > siz[y]) swap(x, y);
trees--;
par[x] = y;
siz[y] += siz[x];
es[y] += es[x];
}
bool same(int x, int y) { return root(x) == root(y); }
int size(int x) { return siz[root(x)]; }
int esize(int x) { return es[root(x)]; }
//つながりを無向グラフと見なし、xが閉路に含まれるか判定
bool close(int x) { return esize(x) >= size(x); }
/*@formatter:off*/V<vi> sets() {vvi(res, trees); umap<int, vi> map; rep(i, n) map[root(i)].push_back(i); int i = 0; for (auto &&p:map) { int r = p.fi; res[i].push_back(r); for (auto &&v:p.se) { if (r == v)continue; res[i].push_back(v); } ++i; } return res; }
};
using bint =__int128;
using u32 = unsigned;
using u64 = unsigned long long;
using u128 = __uint128_t;
std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest;}
//__int128 toi128(string &s) { __int128 ret = 0; for (int i = 0; i < s.length(); ++i) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret;}
//エラー
void ole() {
#ifdef _DEBUG
debugline("ole");exit(0);
#endif
string a = "a";rep(i, 30)a += a;rep(i, 1 << 17)cout << a << endl;cout << "OLE 出力長制限超過" << endl;exit(0);
}
void re() { assert(0 == 1);exit(0); }
void tle() { while (inf)cout << inf << endl; }
//便利関数
#define unique(v) v.erase( unique(v.begin(), v.end()), v.end() );
//[i] := i番として圧縮されたものを返す
vi compress(vi &a) { vi b; int len = a.size(); for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); unique(b); for (int i = 0; i < len; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin(); } int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;}
vi compress(vi &a, umap<int, int> &map) { vi b; int len = a.size(); for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); unique(b); for (int i = 0; i < len; ++i) { int v = a[i]; a[i] = lower_bound(all(b), a[i]) - b.begin(); map[v] = a[i]; } int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;}
vi compress(vi &a, vi &r) { vi b; int len = a.size(); fora(v, a)b.push_back(v); fora(v, r)b.push_back(v); sort(b); unique(b); for (int i = 0; i < len; ++i) a[i] = lower_bound(all(b), a[i]) - b.begin(); for (int i = 0; i < sz(r); ++i) r[i] = lower_bound(all(b), r[i]) - b.begin(); int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;}
vi compress(vi &a, vi &r, vi &s) { vi b; int len = a.size(); fora(v, a)b.push_back(v); fora(v, r)b.push_back(v); fora(v, s)b.push_back(v); sort(b); unique(b); for (int i = 0; i < len; ++i) a[i] = lower_bound(all(b), a[i]) - b.begin(); for (int i = 0; i < sz(r); ++i) r[i] = lower_bound(all(b), r[i]) - b.begin(); for (int i = 0; i < sz(s); ++i) r[i] = lower_bound(all(b), s[i]) - b.begin(); int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;}
vi compress(V<vi> &a) { vi b; fora(vv, a)fora(v, vv)b.push_back(v); sort(b); unique(b); fora(vv, a)fora(v, vv)v = lower_bound(all(b), v) - b.begin(); int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;}
vi compress(vector<vector<vi >> &a) { vi b; fora(vvv, a)fora(vv, vvv)fora(v, vv)b.push_back(v); sort(b); unique(b); fora(vvv, a)fora(vv, vvv)fora(v, vv)v = lower_bound(all(b), v) - b.begin(); int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;}
void compress(int a[], int len) { vi b; for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); unique(b); for (int i = 0; i < len; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin(); }}
//要素が見つからなかったときに困る
#define binarySearch(a, v) (binary_search(all(a),v))
#define lowerIndex(a, v) (lower_bound(all(a),v)-a.begin())
#define lowerBound(a, v) (*lower_bound(all(a),v))
#define upperIndex(a, v) (upper_bound(all(a),v)-a.begin())
#define upperBound(a, v) (*upper_bound(all(a),v))
template<class T> void fin(T s) { cout << s << endl, exit(0); }
#define MIN(a) numeric_limits<a>::min()
#define MAX(a) numeric_limits<a>::max()
//@起動時
struct initon {
initon() {
cin.tie(0);
ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(16);
srand((unsigned) clock() + (unsigned) time(NULL));
};
} initonv;//@formatter:on
//gra mint pr
//上下左右
const string udlr = "udlr";
string UDLR = "UDLR";//x4と連動 UDLR.find('U') := x4[0]
//右、上が正
constexpr int y4[] = {1, -1, 0, 0};
constexpr int x4[] = {0, 0, -1, 1};
constexpr int y8[] = {0, 1, 0, -1, -1, 1, 1, -1};
constexpr int x8[] = {1, 0, -1, 0, 1, -1, 1, -1};
int n, m, k, d, H, W, x, y, z, q;
int cou;
vi t, a, b, c;
//vvi (s, 0, 0);
vvc (ba, 0, 0);
vp p;
str s;
struct pbds_sum {
//@formatter:off
template<typename T = int> class BIT {
public:
int n; vector<T> dat; BIT(int n) : n(n) { dat.assign(n, 0); } T sum(int k) { if (k >= n) k = n - 1; T ret = 0; for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += dat[x]; } return ret; } T sum(int l, int r) { return sum(r) - sum(l); } T get(int l, int r) { return sum(r) - sum(l); } T get(int k) { return sum(k); } T operator[](int k) { assert(0 <= k && k < n); return sum(k + 1) - sum(k); } T operator()(int k) { return sum(k); } T operator()(int l, int r) { return sum(l, r); } void add(int k, T val = 1) { for (int x = k; x < n; x |= x + 1)dat[x] += val; } void update(int k, T val = 0) { add(k, -operator[](k) + val); } void del(int k) { update(k, 0); } void clear() { fill(dat, 0); } void debu() {
#ifdef _DEBUG
vi res; rep(i, min(10ll, n)) { res.push_back(operator[](i)); } deb(res);
#endif
}
int lower_bound(int w) { if (w <= 0) return -1; int x = 0; int k = 1; while ((k << 1) <= n) k <<= 1; for (; k > 0; k >>= 1) { if (x + k <= n && dat[x + k - 1] < w) { w -= dat[x + k - 1]; x += k; } } return x; }
};
BIT<int> bco, bsu;
umapi v_i;
vi i_v;
int count = 0;
//@formatter:on
//クエリの順番が分かってる場合の高速化はとりあえずしない(十分高速なため)
//クエリの順番が入れ替わってもいいようにする
pbds_sum(vi &a) : bco(sz(a) + 3), bsu(sz(a) + 3) {
vi b = a;
b.push_back(linf + 100);
i_v = compress(b);
rep(i, sz(a)) { v_i[a[i]] = b[i]; }
}
pbds_sum(vi &a, vi &b) : bco(sz(a) + sz(b) + 3), bsu(sz(a) + sz(b) + 3) {
vi c = a;
vi d = b;
c.push_back(linf + 100);
d.push_back(linf + 100);
i_v = compress(c, d);
rep(i, sz(a)) {
v_i[a[i]] = c[i];
v_i[b[i]] = d[i];
}
}
pbds_sum(vi &a, vi &b, vi &c) : bco(sz(a) + sz(b) + sz(c) + 3), bsu(sz(a) + sz(b) + sz(c) + 3) {
vi d = a;
vi e = b;
vi f = c;
d.push_back(linf + 100);
e.push_back(linf + 100);
f.push_back(linf + 100);
i_v = compress(d, e, f);
rep(i, sz(a)) {
v_i[a[i]] = d[i];
v_i[b[i]] = e[i];
v_i[c[i]] = f[i];
}
}
void add(int v, int c = 1) {
count += c;
int ind = v_i[v];
bco.add(ind, c);
bsu.add(ind, v * c);
}
void add(vi &a) {
fora(v, a)add(v);
}
//開区間
int sum() { return bsu.sum(inf); }
int sum(int rv) {
int i = (std::lower_bound(all(i_v), rv) - i_v.begin());
return bsu.sum(i);
}
//半開区間 l rは存在しない値でもいい
int sum(int l, int r) { return sum(r) - sum(l); }
//クエリ候補全ての中でのi
int sum_i(int li, int ri) { return bsu.sum(ri) - bsu.sum(li); }
int cou(int rv) {
int i = (std::lower_bound(all(i_v), rv) - i_v.begin());
return bco.sum(i);
}
//半開区間 l rは存在しない値でもいい
int cou(int l, int r) { return cou(r) - cou(l); }
int cou_i(int ri) { return bco.sum(ri); }
int cou_i(int li, int ri) { return bco.sum(ri) - bco.sum(li); }
//k番目の要素を返す
int find_by_order(int k) {
int i = bco.lower_bound(k + 1);
if (i >= sz(i_v)) {
cerr << "find_by_order(" << k << ") k >=" << count << "(count)" << endl;
exit(0);
}
return i_v[i];
}
//vは何番目に入るか
int order_by_key(int v) {
v = *std::lower_bound(all(i_v), v);
int i = v_i[v];
return bco.sum(i);
}
//中央値を返す (左寄り)
int mid() { return find_by_order((count - 1) / 2); }
int mid(int lv, int rv) {
int lcou = cou(lv);
int rcou = cou(rv);
int wantk = lcou + ((rcou - lcou - 1) / 2);
return find_by_order(wantk);
}
int mid_i(int li, int ri) {
int lcou = bco.sum(li);
int rcou = bco.sum(ri);
int wantk = lcou + ((rcou - lcou - 1) / 2);
return find_by_order(wantk);
}
int mid_i(int ri) { return mid_i(0, ri); }
//全要素との 最小の差の和をかえす (全要素の中央値との差の和)
int min_dis() {
int mv = mid();
int mi = v_i[mv];
int lcou = bco.sum(mi);
int rcou = bco.sum(mi + 1, linf);
int lsum = mv * lcou - bsu.sum(mi);
int rsum = bsu.sum(mi + 1, linf) - mv * rcou;
return lsum + rsum;
}
int min_dis(int lv, int rv) {
int li = (std::lower_bound(all(i_v), lv) - i_v.begin());
int ri = (std::lower_bound(all(i_v), rv) - i_v.begin());
int mv = mid_i(li, ri);
int mi = v_i[mv];
int lcou = cou_i(li, mi);
int rcou = cou_i(mi, ri);
return mv * lcou - sum_i(li, mi) + sum_i(mi, ri) - mv * rcou;
}
//@formatter:on
int min_dis_i(int li, int ri) {
int mv = mid_i(li, ri);
int mi = v_i[mv];
int lcou = cou_i(li, mi);
int rcou = cou_i(mi, ri);
return mv * lcou - sum_i(li, mi) + sum_i(mi, ri) - mv * rcou;
}
//vをc個消す
void erase(int v, int c = 1) {
int ind = v_i[v];
assert(bco[ind] >= c);
count -= c;
bco.add(ind, -c);
bsu.add(ind, v * -c);
}
int lower_bound(int v) {
v = *std::lower_bound(all(i_v), v);
int i = v_i[v];
int needc = bco.sum(i) + 1;
i = bco.lower_bound(needc);
return i_v[i];
}
int upper_bound(int v) { return lower_bound(v + 1); }//@formatter:on
};
template<class F> ll goldd_l(ll left, ll right, F calc) {
double GRATIO = 1.6180339887498948482045868343656;
ll lm = left + (ll) ((right - left) / (GRATIO + 1.0));
ll rm = lm + (ll) ((right - lm) / (GRATIO + 1.0));
ll fl = calc(lm);
ll fr = calc(rm);
while (right - left > 10) {
if (fl < fr) {
right = rm;
rm = lm;
fr = fl;
lm = left + (ll) ((right - left) / (GRATIO + 1.0));
fl = calc(lm);
} else {
left = lm;
lm = rm;
fl = fr;
rm = lm + (ll) ((right - lm) / (GRATIO + 1.0));
fr = calc(rm);
}
}
ll minScore = MAX(ll);
ll resIndex = left;
for (ll i = left; i < right + 1; ++i) {
ll score = calc(i);
if (minScore > score) {
minScore = score;
resIndex = i;
}
}
return resIndex;
}
template<class F> ll goldt_l(ll left, ll right, F calc) {
double GRATIO = 1.6180339887498948482045868343656;
ll lm = left + (ll) ((right - left) / (GRATIO + 1.0));
ll rm = lm + (ll) ((right - lm) / (GRATIO + 1.0));
ll fl = calc(lm);
ll fr = calc(rm);
while (right - left > 10) {
if (fl > fr) {
right = rm;
rm = lm;
fr = fl;
lm = left + (ll) ((right - left) / (GRATIO + 1.0));
fl = calc(lm);
} else {
left = lm;
lm = rm;
fl = fr;
rm = lm + (ll) ((right - lm) / (GRATIO + 1.0));
fr = calc(rm);
}
}
if (left > right) {
ll l = left;
left = right;
right = l;
}
ll maxScore = MIN(ll);
ll resIndex = left;
for (ll i = left; i < right + 1; ++i) {
ll score = calc(i);
if (maxScore < score) {
maxScore = score;
resIndex = i;
}
}
return resIndex;
}
//vi dp(k5);//1-indexed
void solve() {
in(n);
na(b, n);
mapi co;
rep(i, n) {
co[b[i]]++;
}
rep(i, n) {
if (co[b[i]] >= 2)con;
a.push_back(b[i]);
}
sort(a);
n = sz(a);
vi dp(n + 1);
pbds_sum s(a);
s.add(a);
int r = 0;
auto calc = [&](int mid) {
int a = s.min_dis_i(mid, r);
int b = dp[mid];
return a + b;
};
if(n==1){
int res=linf;
rep(i, sz(b))if(a[0]!=b[i])res=min(res,abs(a[0]-b[i]));
fin(res);
}
dp[2] = a[1] - a[0];
dp[3] = dp[2] + a[2] - a[1];
if (n < 4) {
fin(dp[n]);
}
for (r = 4; r < n + 1; r++) {
int l = goldd_l(2, r - 2, calc);
dp[r] = calc(l);
}
// cout << dp << endl;
cout << dp[n] << endl;
}
int my(int n, vi &a) {
return 0;
}
int sister(int n, vi &a) {
int ret = 0;
return ret;
}
signed main() {
solve();
return 0;
}