結果
問題 | No.2854 -1 Subsequence |
ユーザー |
|
提出日時 | 2024-08-25 15:39:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 25,954 bytes |
コンパイル時間 | 7,405 ms |
コンパイル使用メモリ | 350,476 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-08-25 15:39:34 |
合計ジャッジ時間 | 9,040 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#pragma GCC optimize("Ofast")#pragma GCC target("avx2")#pragma GCC optimize("unroll-loops")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define rep(i,n) for(ll i = 0LL; i < (ll)n; ++i)#define rep1(i,n) for(ll i = 1LL; i <= (ll)n; ++i)#define rep2(i,m,n) for(ll i = (ll)m; i < (ll)n; ++i)#define rrep(i,n) for(ll i = (ll)n - 1; i >= 0LL; --i)#define rrep1(i,n) for(ll i = (ll)n; i > 0LL; --i)#define rrep2(i,m,n) for(ll i = (ll)m; i > (ll)n; --i)#define lb(a,x) static_cast<ll>(lower_bound(all(a), x) - a.begin())#define ub(a,x) static_cast<ll>(upper_bound(all(a), x) - a.begin())#define all(a) a.begin(), a.end()#define rall(a) a.rbegin(), a.rend()#define SORT(a) sort(all(a));#define RSORT(a) sort(rall(a));#define REV(a) reverse(all(a));#define CEIL(x,y) (x+y-1)/y#define pb push_back#define eb emplace_back#define _GLIBCXX_DEBUG#define _CRT_SECURE_NO_WARNINGS#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)using namespace std;using namespace chrono;using namespace atcoder;using ld = long double;using ll = long long;using ull = unsigned long long;using vi = vector<int>;using vl = vector<ll>;using vc = vector<char>;using vb = vector<bool>;using vs = vector<string>;using vvi = vector<vi>;using vvl = vector<vl>;using vvc = vector<vc>;using vvb = vector<vb>;using vvs = vector<vs>;using pii = pair<int, int>;using pll = pair<ll, ll>;using si = set<int>;using sl = set<ll>;using mii = map<int, int>;using mll = map<ll, ll>;//invoid in(){}template<class T>void in(vector<T> &v){for(T &t : v)cin >> t;}template<class T>void in(vector<vector<T>> &v){for(auto &row : v)for(T&element : row)cin >> element;}template<class Head, class... Tail>void in(Head &head, Tail &...tail){cin >> head; in(tail...);}//outvoid out(){}template<class T>void out(const T &t){cout << t << endl;}template<class T>void out(vector<T> &v){for(T &t : v)cout << t << ' ';cout << endl;}template<class T>void out(vector<vector<T>> &v){for(vector<T> &row : v){for(T &element : row){cout << element << ' ';}cout << endl;}}template<class Head, class...Tail>void out(const Head &head, const Tail &...tail){cout << head; out(tail...);}//chmaxtemplate<typename T>bool chmax(T &a, T b){return((a < b)? (a = b, true) : (false));}//chmintemplate<typename T>bool chmin(T &a, T b){return((a > b)? (a = b, true) : (false));}//mintemplate<typename T>T MIN(vector<T> &v){T mn = numeric_limits<T>::max();for(T &e : v){mn = min(mn, e);}return mn;}//maxtemplate<typename T>T MAX(vector<T> &v){T mx = numeric_limits<T>::min();for(T &e : v){mx = max(mx, e);}return mx;}//sumtemplate<typename T>T SUM(vector<T> &v){T sum = 0;for(T &e : v){sum += e;}return sum;}//l_sorttemplate<typename T>void l_sort(vector<T> &l, vector<T> &r){assert(l.size() == r.size());long long n = l.size();vector<pair<T, T>> p;for(ll i = 0; i < n; i++){p.emplace_back(l[i], r[i]);}sort(p.begin(), p.end());for(ll i = 0; i < n; i++){l[i] = p[i].first;r[i] = p[i].second;}}//r_sorttemplate<typename T>void r_sort(vector<T> &l, vector<T> &r){assert(l.size() == r.size());long long n = l.size();vector<pair<T, T>> p;for(ll i = 0; i < n; i++){p.emplace_back(r[i], l[i]);}sort(p.begin(), p.end());for(ll i = 0; i < n; i++){l[i] = p[i].second;r[i] = p[i].first;}}//-----------------------array-----------------------////cumulative_sumtemplate<typename T> vector<T> cumulative_sum(vector<T> &v){ll n = v.size();vector<T> res(n + 1);for(ll i = 0; i < n; ++i){res[i + 1] = res[i] + v[i];}return res;}//LCSll LCS(string s, string t){vector dp(s.size() + 1,vector<ll>(t.size() + 1));rep(i,s.size()){rep(j,t.size()){if(s[i] == t[j]){dp[i + 1][j + 1] = max({dp[i][j + 1],dp[i + 1][j],dp[i][j] + 1});}else{dp[i + 1][j + 1] = max(dp[i][j + 1],dp[i + 1][j]);}}}return dp[s.size()][t.size()];}//LIStemplate<typename T>ll LIS(vector<T> &a){vector<T> dp;for (T &e : a){auto it = lower_bound(dp.begin(), dp.end(), e);if (it == dp.end()){dp.push_back(e);}else{*it = e;}}return (ll)dp.size();}template< typename T > struct Compress {vector< T > xs;Compress() = default;Compress(const vector< T > &vs) {add(vs);}Compress(const initializer_list< vector< T > > &vs) {for(auto &p : vs) add(p);}void add(const vector< T > &vs) {copy(begin(vs), end(vs), back_inserter(xs));}void add(const T &x) {xs.emplace_back(x);}void build() {sort(begin(xs), end(xs));xs.erase(unique(begin(xs), end(xs)), end(xs));}vector< ll > get(const vector< T > &vs) const {vector< ll > ret;transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {return lower_bound(begin(xs), end(xs), x) - begin(xs);});return ret;}ll get(const T &x) const {return lower_bound(begin(xs), end(xs), x) - begin(xs);}const T &operator[](ll k) const {return xs[k];}};ll edit_distance(string &s, string &t){ll n = s.size(), m = t.size();vector dp(n + 1, vector<ll>(m + 1));for(ll i = 1; i <= n; i++)dp[i][0] = i;for(ll j = 1; j <= m; j++)dp[0][j] = j;for(ll i = 1; i <= n; i++)for(ll j = 1; j <= m; j++){dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (s[i - 1] == t[j - 1]? 0 : 1)});}return dp[n][m];}//--------------------data_structure-----------------////suffix_arraystruct suffix_array{vector<ll> sa, rank, tmp;ll n;string base;//suffix_arrayを構築suffix_array(const string s){n = s.size();base = s;sa.resize(n);rank.resize(n);tmp.resize(n);for(ll i = 0; i < n; i++){sa[i] = i;rank[i] = s[i];}for(ll k = 1; k < n; k *= 2){auto compare_sa = [&](ll i, ll j){if(rank[i] != rank[j])return rank[i] < rank[j];ll ri = (i + k < n) ? rank[i + k] : -1;ll rj = (j + k < n) ? rank[j + k] : -1;return ri < rj;};sort(sa.begin(), sa.end(), compare_sa);tmp[sa[0]] = 0;for(ll i = 1; i < n; i++){tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i])? 1 : 0);}rank = tmp;}}//部分文字列の個数を求めるll get_counts(string t){string u = t + "彁";ll num1, num2;{ll m = t.size();ll ng = -1, ok = n;while(ok - ng > 1){ll mid = (ng + ok) / 2;ll l = sa[mid];if(base.substr(l, m) >= t){ok = mid;}else{ng = mid;}}num1 = ok;}{ll m = u.size();ll ng = -1, ok = n;while(ok - ng > 1){ll mid = (ng + ok) / 2;ll l = sa[mid];if(base.substr(l, m) >= u){ok = mid;}else{ng = mid;}}num2 = ok;}return num2 - num1;}};//-----------------------check-----------------------////is_primetemplate<typename T> bool is_prime(T n){if(n <= 1)return false;T m = sqrt(n);for(ll i = 2; i <= m; ++i){if(n % i == 0)return false;}return true;}//is_squaretemplate<typename T> bool is_square(T n){if(n < 0)return false;T m = sqrt(n);if(n == m * m){return true;}else{return false;}}//is_substringbool is_substring(const string& s, const string& t){const ll n = s.size(), m = t.size();for(ll i = 0; i + m <= n; ++i){if(s.substr(i, m) == t)return true;}return false;}//-----------------------math------------------------////gcd(faster)ll GCD(ll A, ll B){if(B == 0){return A;}else{return GCD(B, A % B);}}//lcm(faster)ll LCM(ll A, ll B){return A / GCD(A, B) * B;}//combll comb(ll n, ll r){assert(n >= 2);vector dp(n + 1, vector<ll>(r + 1));for(ll i = 0; i < n + 1; ++i){dp[i][0] = 1;}for(ll i = 0; i < r + 1; ++i){dp[i][i] = 1;}for(ll i = 1; i < n + 1; ++i){for(ll j = 1; j < min(i, r + 1); ++j){dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}}return dp[n][r];}// comb_modusing mint_comb = atcoder::static_modint<1000000007>;vector<mint_comb> fac, finv, inv;// テーブルを作る前処理void init_comb_mod(ll size) {size += 109;fac.resize(size);finv.resize(size);inv.resize(size);const ll MOD = mint_comb::mod();fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (ll i = 2; i < size; i++){fac[i] = fac[i - 1] * i;inv[i] = MOD - inv[MOD%i] * (MOD / i);finv[i] = finv[i - 1] * inv[i];}}// 二項係数計算mint_comb comb_mod(ll n, ll k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * finv[k] * finv[n - k];}//make_random//long longll rand_ll(ll l, ll r){if(l > r)swap(l, r);random_device rd;mt19937_64 gen(rd());uniform_int_distribution<ll>dis(l, r);return dis(gen);}//intint rand_int(int l, int r){if(l > r)swap(l, r);return l + rand() % (r - l + 1);}//doubleld rand_double(){return (ld)1.0 * rand() / RAND_MAX;}//base_conversionll ntodec(const char c){if(c >= '0' && c <= '9'){return (ll)c - '0';}else{return (ll)c - 55;}}char decton(const ll n){if(n >= 0 && n <= 9){return (char)'0' + n;}else{return (char)55 + n;}}inline ll pow_ll(ll x,ll n){ll ret = 1;rep(i,n){ret *= x;}return ret;}string base_conversion(string str, ll n, ll m){ull tmp = 0;string ret;rep(i,str.size()){tmp += (ull)ntodec(str[str.size() - 1 - i]) * pow_ll(n, i);}if(tmp == 0){return "0";}while(tmp != 0){ret = decton(tmp % m) + ret;tmp /= m;}return ret;}//calc_trianglelong double calc_triangle(long double x1,long double y1,long double x2,long double y2,long double x3,long double y3){return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);}//文字列の最小周期vector<ll> computeLPSArray(const string& pattern) {ll m = pattern.length();vector<ll> lps(m);ll len = 0;lps[0] = 0;ll i = 1;while (i < m) {if (pattern[i] == pattern[len]) {len++;lps[i] = len;i++;} else {if (len != 0) {len = lps[len - 1];} else {lps[i] = 0;i++;}}}return lps;}ll findMinimumPeriod(const string& str) {ll n = str.length();vector<ll> lps = computeLPSArray(str);ll len = lps[n - 1];ll period = n - len;if (n % period == 0) {return period;} else {return n;}}//-----------------------graph-----------------------////graph_templatestruct Edge{ll to;ll cost;Edge(ll to, ll cost) : to(to), cost(cost) {}bool operator>(const Edge &e) const{return cost > e.cost;}bool operator<(const Edge &e) const{return cost < e.cost;}};struct Edge2{ll from;ll to;ll cost;Edge2(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {}bool operator>(const Edge2 &e) const{return cost > e.cost;}bool operator<(const Edge2 &e) const{return cost < e.cost;}};struct Edge3 {ll to;Edge3(ll to) : to(to) {}};struct Graph{Graph() = default;vector<vector<Edge>> G;Graph(ll N){G.resize(N);}ll size(){return G.size();}void add_edge(ll from, ll to, ll cost = 1){G[from].push_back(Edge(to, cost));G[to].push_back(Edge(from, cost));}void add_directed_edge(ll from, ll to, ll cost = 1){G[from].push_back(Edge(to, cost));}vector<Edge> &operator[](ll v){return G[v];}};//dijkstrastruct dijkstra{vector<ll> dist;vector<ll> prev;//dijkstraを構築dijkstra(Graph &G, ll s){ll N = G.size();dist.assign(N, 1LL << 60);prev.assign(N, -1);priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;dist[s] = 0;pq.emplace(dist[s], s);while (!pq.empty()){auto p = pq.top();pq.pop();ll v = p.second;if(dist[v] < p.first)continue;for (auto &e : G[v]){if (dist[e.to] > dist[v] + e.cost){dist[e.to] = dist[v] + e.cost;prev[e.to] = v;pq.emplace(dist[e.to], e.to);}}}}//最小コストを求めるll get_cost(ll to){return dist[to];}//最短経路を求めるvector<ll> get_path(ll to){vector<ll> get_path;for (ll i = to; i != -1; i = prev[i]){get_path.push_back(i);}reverse(get_path.begin(), get_path.end());return get_path;}//到達可能か調べるbool cango(ll to){return dist[to] != 1LL << 60;}};//bellman_fordstruct bellman_ford{vector<ll> dist;vector<ll> prev;ll start;ll n;bool cl = false;//bellman_fordを構築bellman_ford(Graph &g, ll s){start = s;n = g.size();dist.assign(n, 1LL << 60);prev.assign(n, -1);vector<ll> counts(n);vector<bool> inqueue(n);queue<ll> q;dist[s] = 0;q.push(s);inqueue[s] = true;while(!q.empty()){ll from = q.front();q.pop();inqueue[from] = false;for(auto &e : g[from]){ll d = dist[from] + e.cost;if(d < dist[e.to]){dist[e.to] = d;prev[e.to] = from;if(!inqueue[e.to]){q.push(e.to);inqueue[e.to] = true;++counts[e.to];if(n < counts[e.to])cl = true;}}}}}//最小コストを求めるll get_cost(ll to){return dist[to];}//最短経路を求めるvector<ll> get_path(ll to){vector<ll> path;if(dist[to] != 1LL << 60){for(ll i = to; i != -1; i = prev[i]){path.push_back(i);}reverse(path.begin(), path.end());}return path;}//到達可能か調べるbool cango(ll to){return (dist[to] != 1LL << 60);}//負の閉路の有無を調べるbool closed(){return cl;}};//warshall_floydstruct warshall_floyd{vector<vector<ll>> d;vector<vector<ll>> next;bool cl = false;//warshall_floydを構築warshall_floyd(Graph &g){ll n = g.size();d.resize(n, vector<ll>(n, 1LL << 60));next.resize(n, vector<ll>(n, -1));for(ll i = 0; i < n; i++){d[i][i] = 0;}for(ll i = 0; i < n; i++){for(auto e : g[i]){d[i][e.to] = e.cost;next[i][e.to] = e.to;}}for(ll k = 0; k < n; ++k){for(ll i = 0; i < n; ++i){for(ll j = 0; j < n; ++j){if(d[i][k] == 1LL << 60 || d[k][j] == 1LL << 60)continue;if(d[i][j] > d[i][k] + d[k][j]){d[i][j] = d[i][k] + d[k][j];next[i][j] = next[i][k];}}}}for(ll i = 0; i < n; i++){if(d[i][i] < 0){cl = true;break;}}}//最小コストを求めるll get_cost(ll from, ll to){return d[from][to];}//最短経路を求めるvector<ll> get_path(ll from, ll to) {if (d[from][to] == 1LL << 60) return {};vector<ll> path;for(ll at = from; at != to; at = next[at][to]){if (at == -1) return {};path.push_back(at);}path.push_back(to);return path;}//到達可能か調べるbool cango(ll from, ll to){return d[from][to] != 1LL << 60;}//負の閉路の有無を調べるbool closed(){return cl;}};//UnionFindstruct UnionFind{vector<ll>par, rank, siz;UnionFind(ll n):par(n, -1), rank(n, 0), siz(n, 1){}ll root(ll x){if(par[x] == -1){return x;}else{return par[x] = root(par[x]);}}//連結判定bool issame(ll x, ll y){return root(x) == root(y);}//連結bool unite(ll x, ll y){ll rx = root(x), ry = root(y);if(rx == ry){return false;}if(rank[rx] < rank[ry]){swap(rx, ry);}par[ry] = rx;if(rank[rx] == rank[ry]){rank[rx]++;}siz[rx] += siz[ry];return true;}ll size(ll x){return siz[root(x)];}};struct kruskal{ll n;vector<Edge2> edges;//kruskalの構築kruskal(Graph &g){n = g.size();for(ll i = 0; i < n; i++){for(auto e : g[i]){edges.emplace_back(i, e.to, e.cost);}}}//最小全域木のコストを求めるll get_mincost(){sort(edges.begin(), edges.end());UnionFind uf(n);ll ret = 0;for(auto e : edges){if(uf.unite(e.from, e.to))ret += e.cost;}return ret;}//最大全域木のコストを求めるll get_maxcost(){sort(edges.rbegin(), edges.rend());UnionFind uf(n);ll ret = 0;for(auto e : edges){if(uf.unite(e.from, e.to))ret += e.cost;}return ret;}};//木の直径を求めるll tree_diameter(Graph g){ll n = g.size();dijkstra d(g, 0);ll mx = 0, idx = -1;for(ll i = 0; i < n; i++){if(mx < d.get_cost(i)){mx = d.get_cost(i);idx = i;}}dijkstra d2(g, idx);ll mx2 = 0;for(ll i = 0; i < n; i++){if(mx2 < d2.get_cost(i)){mx2 = d2.get_cost(i);}}return mx2;}//LCAstruct LCA {vector<vector<ll>> parent; // parent[k][u]:= u の 2^k 先の親vector<ll> dist; // root からの距離LCA(Graph &g, ll root = 0){vector<vector<Edge3>> G(g.size());for(ll i = 0; i < g.size(); i++){for(auto e : g[i]){G[i].emplace_back(e.to);}}ll V = G.size();ll K = 1;while ((1 << K) < V) K++;parent.assign(K, vector<ll>(V, -1));dist.assign(V, -1);dfs(G, root, -1, 0);for (ll k = 0; k + 1 < K; k++) {for (ll v = 0; v < V; v++) {if (parent[k][v] < 0) {parent[k + 1][v] = -1;} else {parent[k + 1][v] = parent[k][parent[k][v]];}}}}void dfs(const vector<vector<Edge3>> &G, ll v, ll p, ll d) {parent[0][v] = p;dist[v] = d;for (auto e : G[v]) {if (e.to != p) dfs(G, e.to, v, d + 1);}}ll query(ll u, ll v) {if (dist[u] < dist[v]) swap(u, v); // u の方が深いとするll K = parent.size();// LCA までの距離を同じにするfor (ll k = 0; k < K; k++) {if ((dist[u] - dist[v]) >> k & 1) {u = parent[k][u];}}// 二分探索で LCA を求めるif (u == v) return u;for (ll k = K - 1; k >= 0; k--) {if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}}return parent[0][u];}ll get_dist(ll u, ll v){return dist[u] + dist[v] - 2 * dist[query(u, v)];}bool is_on_path(ll u, ll v, ll a){return get_dist(u, a) + get_dist(a, v) == get_dist(u, v);}};struct AuxiliaryTree {vector<vector<ll>> G0;LCA &lca;AuxiliaryTree(LCA &lca) : lca(lca) {}void build(ll k, vector<ll> &vs) {sort(vs.begin(), vs.begin() + k, [&](ll a, ll b) { return lca.dist[a] < lca.dist[b]; });stack<ll> stk;stk.push(vs[0]);G0[vs[0]].clear();for (ll i = 1; i < k; ++i) {ll w = lca.query(vs[i - 1], vs[i]);if (w != vs[i - 1]) {ll last = stk.top(); stk.pop();while (!stk.empty() && lca.dist[w] < lca.dist[stk.top()]) {G0[stk.top()].push_back(last);last = stk.top(); stk.pop();}if (stk.empty() || stk.top() != w) {stk.push(w);vs.push_back(w);G0[w] = { last };} else {G0[w].push_back(last);}}stk.push(vs[i]);G0[vs[i]].clear();}while (stk.size() > 1) {ll u = stk.top(); stk.pop();G0[stk.top()].push_back(u);}}};//centroid_decompositionstruct centroid_decomposition{Graph g;ll n;vector<ll> size;ll centroid;centroid_decomposition(Graph f) : g(f){g = f;n = g.size();size.resize(n, 1);stack<tuple<ll, ll, ll>> st;st.push({0, 0, 0});while (!st.empty()) {ll v, p, t;tie(v, p, t) = st.top();st.pop();if (t == 0) {st.push({v, p, 1});for (auto [c, d] : g[v]) {if (c != p) {st.push({c, v, 0});}}} else {bool is_centroid = true;for (auto [c, d] : g[v]) {if (c != p) {size[v] += size[c];if (size[c] > n / 2) {is_centroid = false;}}}if (is_centroid && n - size[v] <= n / 2) {centroid = v;}}}}//木の重心を求めるll get_centroid(){return centroid;}//重心によって分解された部分木を求めるvector<vector<ll>> get_subtree(){vector<vector<ll>> comp(n);stack<tuple<ll, ll, ll>> st;for(auto [v, w] : g[centroid]){st.push({v, centroid, v});}while(!st.empty()){auto[v, p, i] = st.top();st.pop();comp[i].push_back(v);for(auto [c, d] : g[v]){if(c != p){st.push({c, v, i});}}}return comp;}};//----------------------normal-----------------------//const ld PI = 3.1415926535897932;const ll mod = 998244353;const ll MOD = 1000000007;const ll dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};const ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1};const string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";const string alpha = "abcdefghijklmnopqrstuvwxyz";//using mint = modint;//using mint = static_modint<1777777777>;using mint = modint998244353;//using mint = modint1000000007;/*-----------------------function------------------------*//*------------------------solve--------------------------*/void solve(){ll n; cin >> n;vector dp(2, vector<ll>(n + 1));dp[0][0] = 0;dp[1][0] = -5e18;bool ok = 0;ll mn = 8e18;rep(i,n){ll a; cin >> a;chmin(mn, a);if(dp[0][i] <= dp[1][i] + a){dp[0][i + 1] = dp[1][i] + a;ok = 1;}else{dp[0][i + 1] = dp[0][i];}dp[1][i + 1] = max(dp[1][i], dp[0][i] - a);}if(ok){cout << max(dp[0][n], dp[1][n]) << endl;}else{cout << -mn << endl;}}int main(){cin.tie(nullptr);cout.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(20);srand((unsigned)time(NULL));//ll T; cin >> T;ll T = 1;while(T--){solve();}return 0;}