結果
| 問題 | No.3017 交互浴 |
| ユーザー |
 ゆうき
|
| 提出日時 | 2025-02-05 14:26:02 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 828 ms / 2,000 ms |
| コード長 | 44,255 bytes |
| コンパイル時間 | 11,028 ms |
| コンパイル使用メモリ | 97,952 KB |
| 実行使用メモリ | 60,032 KB |
| 最終ジャッジ日時 | 2025-02-05 14:26:53 |
| 合計ジャッジ時間 | 48,551 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 55 |
ソースコード
import static java.lang.Math.*;import static java.util.Arrays.*;import java.io.*;import java.lang.reflect.*;import java.util.*;import java.util.ArrayList;import java.util.concurrent.*;import java.util.function.*;public final class Main{public static void main(String[] args) throws Exception{MyReader in = new MyReader(System.in);MyWriter out = new MyWriter(System.out,false),log = new MyWriter(System.err,true);int T = Solver.multi ? in.it() : 1;while (T-- > 0)Optional.ofNullable(new Solver(in,out,log).solve()).ifPresent(out::println);out.flush();}}class Solver extends BaseSolver{public Solver(MyReader in,MyWriter out,MyWriter log){ super(in,out,log); }public static boolean multi = false;public Object solve(){int N = in.it();int[] H = in.it(N);RangeSet rs = new RangeSet();for (int i = 0;i < N;i++) {if (i %2 == 0)rs.add(0,H[i]);elsers.remove(0,H[i]);out.println(rs.size());}return null;}char[][] trans(char[]... T){char[][] ret = new char[T[0].length][T.length];for (int i = 0;i < T.length;i++)for (int j = 0;j < T[0].length;j++)ret[j][i] = T[i][j];return ret;}int max(int... arr){int ret = -infI;for (var a:arr)ret = Math.max(ret,a);return ret;}long min(long... arr){long ret = infL;for (var a:arr)ret = Math.min(ret,a);return ret;}long max(long... arr){long ret = -infL;for (var a:arr)ret = Math.max(ret,a);return ret;}void reverse(Object arr){if (!arr.getClass().isArray())throw new UnsupportedOperationException("reverse");int l = 0;int r = Array.getLength(arr) -1;while (l < r) {Object t = Array.get(arr,l);Array.set(arr,l,Array.get(arr,r));Array.set(arr,r,t);l++;r--;}}}class Data extends BaseV{long v;public Data(long v){ this.v = v; }}class SCC extends Graph<Object>{private Graph<?> g;private MyList<MyList<Integer>> scc;private int counter;private int[] label;private boolean[] seen;public SCC(Graph<?> g){super(g.n,true);this.g = g;scc = new MyList<>();counter = n;label = new int[n];seen = new boolean[n];for (int i = 0;i < n;i++)dfs(i);seen = new boolean[n];for (var t:label) {if (seen[t])continue;MyList<Integer> list = new MyList<>();dfs2(list,t);scc.add(list);}int[] map = new int[n];for (int i = 0;i < scc.size();i++)for (var j:scc.get(i))map[j] = i;Set<Long> set = new HashSet<>();for (var e:g.es) {var u = map[e.u];var v = map[e.v];if (u != v && set.add((long) u <<30 |v))addEdge(u,v);}n = scc.size();}private void dfs(final int i){if (seen[i])return;seen[i] = true;for (var e:g.go(i))dfs(e.v);label[--counter] = i;}private void dfs2(MyList<Integer> set,int i){if (seen[i])return;set.add(i);seen[i] = true;for (var e:g.bk(i))dfs2(set,e.v);}public MyList<Integer> us(int u){ return scc.get(u); }}class RangeSet{private long sz;private TreeSet<long[]> set;public RangeSet(){set = new TreeSet<>(Comparator.comparing(t -> t[0]));long inf = Solver.infL;set.add(new long[]{-inf, -inf});set.add(new long[]{inf, inf});}public long size(){ return sz; }public long add(long x){ return add(x,x +1); }public long add(long l,long r){long ret = r -l;long[] t = {l, r};for (var s = set.floor(t);t[0] <= s[1];s = set.floor(t))ret -= add(t,s);for (var s = set.ceiling(t);s[0] <= t[1];s = set.ceiling(t))ret -= add(t,s);sz += ret;set.add(t);return ret;}public long remove(long x){ return remove(x,x +1); }public long remove(long l,long r){long ret = 0;long[] t = {l, r};for (var s = set.floor(t);l < s[1];s = set.floor(t))ret += remove(t,s);for (var s = set.ceiling(t);s[0] < r;s = set.ceiling(t))ret += remove(t,s);sz -= ret;return ret;}private long add(long[] t,long[] s){long ret = min(t[1],s[1]) -max(t[0],s[0]);set.remove(s);t[0] = min(t[0],s[0]);t[1] = max(t[1],s[1]);return ret;}private long remove(long[] t,long[] s){set.remove(s);long ret = min(t[1],s[1]) -max(t[0],s[0]);if (s[0] < t[0])set.add(new long[]{s[0], t[0]});if (t[1] < s[1])set.add(new long[]{t[1], s[1]});return ret;}public long[] get(long x){long[] ret = set.floor(new long[]{x});return x < ret[1] ? ret : null;}public long mex(){var t = get(0);return t == null ? 0 : t[1];}@Overridepublic String toString(){List<String> list = new ArrayList<>();for (var s:set)list.add(Arrays.toString(s));return list.toString();}}class Permutation{private int n;int[] arr;public Permutation(int n){ arr = Util.arrI(this.n = n,i -> i); }public Permutation(int[] arr){ this.arr = copyOf(arr,n = arr.length); }public boolean increment(){ return crement(1); }public boolean decrement(){ return crement(-1); }private boolean crement(int d){int l = n -2;while (0 <= l && arr[l] *d >= arr[l +1] *d)l--;if (l < 0)return false;int r = n -1;while (arr[l] *d >= arr[r] *d)r--;swap(l,r);l++;r = n -1;while (l < r)swap(l++,r--);return true;}private void swap(int l,int r){arr[l] ^= arr[r];arr[r] ^= arr[l];arr[l] ^= arr[r];}}abstract class SegmentTree<V extends BaseV, F> extends Seg<V, F>{public SegmentTree(int n){ super(n); }@Overrideprotected F comp(F f,F g){ return null; }@Overridepublic void upd(int i,F f){super.upd(i,f);up(i,i +1);}}abstract class Seg<V extends BaseV, F> {private int n,log;private V[] val;private F[] lazy;protected Seg(int n){this.n = n;while (1 <<log <= n)log++;val = Util.cast(new BaseV[n <<1]);lazy = Util.cast(new Object[n]);for (int i = -1;++i < n;)(val[i +n] = init(i)).sz = 1;for (int i = n;--i > 0;merge(i))(val[i] = e()).sz = val[i <<1].sz +val[i <<1 |1].sz;}public void upd(int i,F f){ prop(i +n,f); }public void upd(int l,int r,F f){for (l += n,r += n;l < r;l >>= 1,r >>= 1) {if ((l &1) == 1)prop(l++,f);if ((r &1) == 1)prop(--r,f);}}public V get(int i){ return val[i +n]; }public V get(int l,int r){V[] ret = Util.cast(new BaseV[]{e(), e()});int i = 0;for (var v:getList(l,r)) {agg(ret[i],ret[i ^1],v);ret[i].sz = ret[i ^= 1].sz +v.sz;}return ret[i ^1];}public V[] getList(int l,int r){int sz = 0;for (int li = l += n,ri = r += n;li < ri;li = li +1 >>1,ri >>= 1)sz += (li &1) +(ri &1);V[] arr = Util.cast(Array.newInstance(e().getClass(),sz));for (int i = 0;l < r;l >>= 1,r >>= 1) {if ((l &1) > 0)arr[i++] = val[l++];if ((r &1) > 0)arr[--sz] = val[--r];}return arr;}public V[] getPath(int i){int sz = 32 -Integer.numberOfLeadingZeros(i +n);V[] arr = Util.cast(Array.newInstance(e().getClass(),sz));for (i += n;0 < i;i >>= 1)arr[--sz] = val[i];return arr;}protected V init(int i){ return e(); }protected abstract V e();protected abstract void agg(V v,V a,V b);protected abstract void map(V v,F f);protected abstract F comp(F f,F g);protected void up(int l,int r){for (l = oddPart(l +n),r = oddPart(r +n);l != r;)merge(l > r ? (l >>= 1) : (r >>= 1));while (1 < l)merge(l >>= 1);}protected void down(int l,int r){int i = log;for (l = oddPart(l +n),r = oddPart(r +n);i > 0;i--) {push(l >>i);push(r >>i);}}private void merge(int i){ agg(val[i],val[i <<1],val[i <<1 |1]); }private void push(int i){if (lazy[i] != null) {prop(i <<1,lazy[i]);prop(i <<1 |1,lazy[i]);lazy[i] = null;}}private void prop(int i,F f){map(val[i],f);if (i < n) {lazy[i] = lazy[i] == null ? f : comp(lazy[i],f);if (val[i].fail) {push(i);merge(i);}}}private int oddPart(int i){ return i /(i &-i); }public int bSearchllr(int l,Predicate<V> judge){V cur = e(),tmp = e();down(l,n);V[] list = getList(l,n);int ri = -1;for (var d:list) {agg(tmp,cur,d);if (judge.test(tmp)) {agg(cur,cur,d);cur = tmp;tmp = e();} else {ri = (l +cur.sz +n) /d.sz;push(ri);break;}}if (ri == -1)return n;ri <<= 1;while (ri < val.length) {agg(tmp,cur,val[ri]);if (judge.test(tmp))return l +cur.sz +val[ri].sz;else {push(ri);ri = ri <<1;}}return n;}}class DualBIT{private int n;private long[] val;public DualBIT(int n){this.n = n +1;val = new long[n +2];}public long agg(long a,long b){ return a +b; }public long inv(long v){ return -v; }public long get(int i){ return sum(i +1); }public void upd(int l,int r,long v){upd(l,v);upd(r,inv(v));}private void upd(int x,long v){for (x++;x <= n;x += x &-x)val[x] = agg(val[x],v);}private long sum(int x){long ret = 0;for (;x > 0;x -= x &-x)ret = agg(ret,val[x]);return ret;}}class Combin{int n = 2;long[] f,fi;long mod = Util.mod;public Combin(int n){this();grow(n);}public Combin(){ f = fi = new long[]{1, 1}; }public void grow(int n){n = min((int) mod,n);f = copyOf(f,n);fi = copyOf(fi,n);for (int i = this.n;i < n;i++)f[i] = f[i -1] *i %mod;fi[n -1] = pow(f[n -1],mod -2);for (int i = n;--i > this.n;)fi[i -1] = fi[i] *i %mod;this.n = n;}private long pow(long x,long n){long ret = 1;for (x %= mod;0 < n;x = x *x %mod,n >>= 1)if ((n &1) == 1)ret = ret *x %mod;return ret;}public long nHr(int n,int r){ return r < 0 ? 0 : nCr(n +r -1,r); }public long nCr(int n,int r){if (r < 0 || n -r < 0)return 0;if (this.n <= n)grow(max(this.n <<1,n +1));return f[n] *(fi[r] *fi[n -r] %mod) %mod;}}abstract class AVLSegmentTree<V extends BaseV, F> {private V e = e();private Node root;private V[] ret = Util.cast(new BaseV[2]);private int ri;public AVLSegmentTree(int n){this();root = new Node(e(),n);}public AVLSegmentTree(){ret[ri] = e();ri = 1;}public void build(int n,IntFunction<V> init){ root = build(0,n,init); }private Node build(int l,int r,IntFunction<V> init){if (r -l == 1)return new Node(init.apply(l),1);var ret = new Node(e(),r -l);ret.lft = build(l,l +r >>1,init);ret.rht = build(l +r >>1,r,init);return ret.update();}public void add(V v){ add(v,1); }public void add(V v,int k){ ins(size(),v,k); }public void ins(int i,V v){ ins(i,v,1); }public void ins(int i,V v,int k){ root = root == null ? new Node(v,k) : ins(root,i,v,k); }private Node ins(Node nd,int i,V v,int k){if (nd.lft == null && (i == 0 || i == nd.sz))split(nd,i == 0 ? 1 : -1,v,k,nd.sz +k);else {if (nd.lft == null)split(nd,1,ag(e(),e,nd.val),i,nd.sz);elsend.push();if (i < nd.lft.sz)nd.lft = ins(nd.lft,i,v,k);elsend.rht = ins(nd.rht,i -nd.lft.sz,v,k);}return balance(nd);}public void del(int i){ root = del(root,i); }private Node del(Node nd,int i){if (nd.lft == null)return 0 < --nd.sz ? nd : null;nd.push();int c = i < nd.lft.sz ? -1 : 1;Node del = c < 0 ? del(nd.lft,i) : del(nd.rht,i -nd.lft.sz);if (del == null)return nd.cld(-c);nd.cld(c,del);return balance(nd);}public void upd(int i,F f){ upd(i,i +1,f); }public void upd(int l,int r,F f){if (size() < r)add(e(),r -size());root = upd(root,l,r,f);}private Node upd(Node nd,int l,int r,F f){if (l == 0 && r == nd.sz)nd.prop(f);else if (l < r) {if (nd.lft == null)split(nd,1,ag(e(),e,nd.val),0 < l ? l : r,nd.sz);elsend.push();if (l < nd.lft.sz)nd.lft = upd(nd.lft,l,min(nd.lft.sz,r),f);if (nd.lft.sz < r)nd.rht = upd(nd.rht,max(0,l -nd.lft.sz),r -nd.lft.sz,f);nd = balance(nd);}return nd;}public void toggle(int l,int r){ root = l < r ? toggle(root,l,r) : root; }private Node toggle(Node nd,int l,int r){nd.push();if (0 < l) {split(nd,l);nd = merge(nd.lft,nd,toggle(nd.rht,0,r -l));} else if (r < nd.sz) {split(nd,r);nd = merge(toggle(nd.lft,l,r),nd,nd.rht);} elsend.toggle();return nd;}private void split(Node nd,int i){if (nd.lft == null)split(nd,1,ag(e(),e,nd.val),i,nd.sz);else {nd.push();if (i < nd.lft.sz) {split(nd.lft,i);var lft = nd.lft;nd.lft = lft.lft;nd.rht = merge(lft.rht,lft,nd.rht);} else if (nd.lft.sz < i) {split(nd.rht,i -nd.lft.sz);var rht = nd.rht;nd.rht = rht.rht;nd.lft = merge(nd.lft,rht,rht.lft);}}}private Node merge(Node lft,Node nd,Node rht){if (abs(lft.rnk -rht.rnk) < 2) {nd.lft = lft;nd.rht = rht;} else if (lft.rnk > rht.rnk) {lft.push();lft.rht = merge(lft.rht,nd,rht);nd = lft;} else if (lft.rnk < rht.rnk) {rht.push();rht.lft = merge(lft,nd,rht.lft);nd = rht;}return balance(nd);}public V get(int i){ return get(root,i); }private V get(Node nd,int i){if (nd.lft == null)return nd.val;nd.push();return i < nd.lft.sz ? get(nd.lft,i) : get(nd.rht,i -nd.lft.sz);}public V get(int l,int r){ret[ri] = e();ri ^= 1;if (root != null)get(root,l,min(r,size()));return ret[ri ^= 1];}private void get(Node nd,int l,int r){if (0 == l && r == nd.sz)ag(ret[ri],ret[ri ^= 1],nd.val());else if (nd.lft == null)ag(ret[ri],ret[ri ^= 1],pw(nd.val,r -l));else {nd.push();if (l < nd.lft.sz)get(nd.lft,l,min(nd.lft.sz,r));if (nd.lft.sz < r)get(nd.rht,max(0,l -nd.lft.sz),r -nd.lft.sz);}}public V all(){ return root == null ? e : root.val(); }public int size(){ return root == null ? 0 : root.sz; }protected abstract V e();protected abstract void agg(V v,V a,V b);protected abstract void map(V v,F f);protected abstract F comp(F f,F g);protected abstract void tog(V v);private V ag(V v,V a,V b){agg(v,a,b);v.sz = a.sz +b.sz;return v;}protected V pow(V a,int n){V ret = e();for (V t = ag(e(),e,a);0 < n;n >>= 1,t = ag(e(),t,t))if (0 < (n &1))ret = ag(e(),ret,t);return ret;}private V pw(V a,int n){V ret = pow(a,n);ret.sz = n;return ret;}private void split(Node nd,int c,V vl,int i,int sz){nd.cld(-c,new Node(vl,i));nd.cld(c,new Node(nd.val,sz -i));nd.val = e();}private Node balance(Node nd){ return (1 < abs(nd.bis = nd.rht.rnk -nd.lft.rnk) ? (nd = rotate(nd)) : nd).update(); }private Node rotate(Node u){var v = u.cld(u.bis);v.push();if (u.bis *v.bis < -1)v = rotate(v);u.cld(u.bis,v.cld(-u.bis));v.cld(-u.bis,u);u.update();return v;}private class Node{private int sz,bis,rnk,tog;private V val;private F laz;private Node lft,rht;private Node(V val,int sz){this.sz = sz;this.val = val;val.sz = 1;}private Node update(){bis = rht.rnk -lft.rnk;rnk = max(lft.rnk,rht.rnk) +1;ag(val,lft.val(),rht.val());sz = val.sz;return this;}private void push(){if (laz != null) {lft.prop(laz);rht.prop(laz);laz = null;}if (0 < tog) {lft.toggle();rht.toggle();tog = 0;}}private void prop(F f){map(val,f);if (lft != null)laz = laz == null ? f : comp(laz,f);}private Node toggle(){bis *= -1;var tn = lft;lft = rht;rht = tn;tog(val);if (lft != null)tog ^= 1;return this;}private Node cld(int c){ return c < 0 ? lft : rht; }private void cld(int c,Node nd){ nd = c < 0 ? (lft = nd) : (rht = nd); }private V val(){ return lft == null && 1 < sz ? pw(val,sz) : val; }}}class FunctionalGraph extends Graph<Integer>{public boolean[] closed;public int[] roots;public FunctionalGraph(int n){super(n,true);closed = new boolean[n];roots = new int[n];}public void build(int[] P){int[] cnt = new int[n];for (int i = 0;i < n;i++)cnt[P[i]]++;int[] stk = new int[n];int sp = 0;for (int i = 0;i < n;i++)if (cnt[i] == 0)stk[sp++] = i;fill(closed,true);while (0 < sp) {int u = stk[--sp];closed[u] = false;if (0 < cnt[P[u]] && --cnt[P[u]] == 0)stk[sp++] = P[u];}int[] root = Util.arrI(n,i -> -1);int rp = 0;for (int i = 0;i < n;i++) {if (root[i] != -1 || !closed[i])continue;int u = i;while (root[u] == -1) {root[u] = i;u = P[u];}roots[rp++] = i;}for (int i = 0;i < n;i++)if (!closed[i])addEdge(closed[P[i]] ? root[P[i]] : P[i],i);roots = Arrays.copyOf(roots,rp);}@Overridepublic int size(){ return n >>1; }public Graph<Integer> createTree(){UnionFind uf = new UnionFind(n);for (var e:es)uf.unite(e.u,e.v);if (uf.num != 1)return null;Graph<Integer> ret = new Graph<>(n,false);for (var e:es)if (e.u < e.v)ret.addEdge(e.u,e.v);return ret;}}class MinCostFlow extends Dijkstra<long[], Long>{private long[] h;public MinCostFlow(int n){super(n,false);h = new long[n];}@Overrideprotected Long zero(){ return 0L; }@Overrideprotected Long inf(){ return Util.infL; }@Overrideprotected Long f(Long l,Edge<long[]> e){ return e.val[1] == 0 ? inf() : l +e.val[0] +h[e.u] -h[e.v]; }@Overrideprotected long[] inv(long[] l){ return new long[]{-l[0], 0}; }public void addEdge(int u,int v,long cost,long cap){ addEdge(u,v,new long[]{cost, cap}); }public long[] flow(int s,int t,long flow){long[] ret = new long[2];while (0 < flow) {calc(s);var path = path(t);if (path.isEmpty())break;long cost = 0;long f = flow;for (var e:path)f = min(f,e.val[1]);for (var e:path) {cost += e.val[0];e.val[1] -= f;e.re.val[1] += f;}flow -= f;ret[0] += cost *f;ret[1] += f;for (int i = 0;i < n;i++)h[i] += get(i);}return ret;}}class UnionFind{int num;protected int[] dat;protected int[] nxt;public UnionFind(int n){dat = new int[n];nxt = new int[n];setAll(nxt,i -> i);fill(dat,-1);num = n;}public int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); }public boolean same(int u,int v){ return root(u) == root(v); }public boolean unite(int u,int v){if ((u = root(u)) == (v = root(v)))return false;if (dat[u] > dat[v]) {u ^= v;v ^= u;u ^= v;}dat[u] += dat[v];dat[v] = u;num--;nxt[u] ^= nxt[v];nxt[v] ^= nxt[u];nxt[u] ^= nxt[v];return true;}public int size(int x){ return -dat[root(x)]; }public int[] getGroup(int x){int[] ret = new int[size(x)];for (int i = 0,c = root(x);i < ret.length;i++)ret[i] = c = nxt[c];return ret;}}class BIT{public int n;private long[] bit;public BIT(int n){ this(new long[n]); }public BIT(long[] A){n = A.length;bit = new long[n +1];for (int i = 1;i <= n;i++) {bit[i] += A[i -1];if (i +(i &-i) <= n)bit[i +(i &-i)] += bit[i];}}public void upd(int x,long v){for (x++;x <= n;x += x &-x)bit[x] += v;}public long sum(int x){long ret = 0;for (;x > 0;x -= x &-x)ret += bit[x];return ret;}public long get(int i){ return get(i,i +1); }public long get(int l,int r){ return sum(r) -sum(l); }}class DynamicUnionFind<K> {int num;private Map<K, K> par,nxt;private Map<K, Integer> size;public DynamicUnionFind(){par = new HashMap<>();nxt = new HashMap<>();size = new HashMap<>();num = 0;}public boolean add(K x){if (par.containsKey(x))return false;par.put(x,x);nxt.put(x,x);size.put(x,1);num++;return true;}public K root(K x){add(x);if (x.equals(par.get(x)))return x;K r = root(par.get(x));par.put(par.get(x),r);return r;}boolean same(K u,K v){ return root(u).equals(root(v)); }boolean unite(K u,K v){if ((u = root(u)).equals(v = root(v)))return false;if (size.get(u) < size.get(v)) {var t = u;u = v;v = t;}par.put(v,u);size.merge(u,size.get(v),Integer::sum);var nu = nxt.get(u);nxt.put(u,nxt.get(v));nxt.put(v,nu);num--;return true;}int size(K x){ return size.get(root(x)); }public K[] getGroup(K x){x = root(x);K[] ret = Util.cast(Array.newInstance(x.getClass(),size.get(x)));for (int i = 0;i < ret.length;i++)ret[i] = x = nxt.get(x);return ret;}}class HLD extends Graph<Object>{private int[] p,hp,l,r;public HLD(int n){super(n,false);p = new int[n];hp = new int[n];l = new int[n];r = new int[n];}public MyList<int[]> auxiliary(MyList<Integer> lis){lis = new MyList<>(lis);lis.add(0);MyList<int[]> ret = new MyList<>();lis.sort(Comparator.comparing(i -> l[i]));for (int i = lis.size() -1;i > 0;i--)lis.add(lca(lis.get(i -1),lis.get(i)));lis.sort(Comparator.comparing(i -> l[i]));MyStack<Integer> stk = new MyStack<>();stk.add(lis.get(0));for (var y:lis) {while (r[stk.peek()] <= l[y])stk.pop();if (!stk.peek().equals(y))ret.add(new int[]{stk.peek(), y});stk.add(y);}return ret;}public MyList<int[]> getPath(int u,int v,int incLca){MyList<int[]> ret = new MyList<>();var lst = itr(u,v,(a,b) -> {ret.add(new int[]{l[a], l[b] +1});return p[a];});ret.add(new int[]{l[lst[0]] +1 -incLca, l[lst[1]] +1});return ret;}public int lca(int u,int v){ return itr(u,v,(a,b) -> p[a])[0]; }private int[] itr(int u,int v,IntBinaryOperator f){while (true) {if (l[u] > l[v]) {var t = u;u = v;v = t;}var h = hp[v];if (l[h] <= l[u])return new int[]{u, v};v = f.applyAsInt(h,v);}}public int ei(int e){ return l[es.get(e).v]; }public int l(int u){ return l[u]; }public int r(int u){ return r[u]; }public void makeTree(int s){MyStack<Integer> stk = new MyStack<>();fill(hp,-1);p[s] = s;stk.add(s);stk.add(s);while (!stk.isEmpty()) {var u = stk.pop();if (r[u] < 1) {r[u] = 1;for (var e:go(u)) {if (e.v == p[u])continue;es.set(e.id,e);p[e.v] = u;stk.add(e.v);stk.add(e.v);}} else if (u != s)r[p[u]] += r[u];}for (int u = 0;u < n;u++) {var go = go(u);for (int i = 1;i < go.size();i++)if (r[u] < r[go.get(0).v] || r[go.get(0).v] < r[go.get(i).v] && r[go.get(i).v] < r[u])go.swap(0,i);}stk.add(s);for (int hid = 0;!stk.isEmpty();) {var u = stk.pop();r[u] += l[u] = hid++;if (hp[u] < 0)hp[u] = u;var go = go(u);for (int i = go.size();i-- > 0;) {var v = go.get(i).v;if (v == p[u])continue;if (i == 0)hp[v] = hp[u];stk.add(v);}}}}abstract class Dijkstra<E, L> extends Graph<E>{private Comparator<L> cmp;private L[] len;private int[] hep,idx;private Edge<E>[] pre;private int sz;public Dijkstra(int n,boolean dir){ this(n,dir,Util.cast(Comparator.naturalOrder())); }public Dijkstra(int n,boolean dir,Comparator<L> cmp){super(n,dir);hep = new int[n];idx = new int[n];this.cmp = cmp;}protected abstract L zero();protected abstract L inf();protected abstract L f(L l,Edge<E> e);public L[] calc(int s){ return calc(s,-1); }public L[] calc(int s,int g){len = Util.arr(Util.cast(Array.newInstance(inf().getClass(),sz = n)),i -> inf());pre = Util.cast(new Edge[n]);setAll(hep,i -> i);setAll(idx,i -> i);len[s] = zero();heapfy(idx[s]);for (int cur;0 < sz && (cur = poll()) != g;)for (var e:go(cur))move(cur,e);return len;}public L get(int t){ return len[t]; }public Deque<Edge<E>> path(int t){Deque<Edge<E>> ret = new ArrayDeque<>();for (;pre[t] != null;t = pre[t].u)ret.addFirst(pre[t]);return ret;}private void move(int cur,Edge<E> e){L l = f(len[cur],e);if (idx[e.v] < sz && cmp.compare(l,len[e.v]) < 0) {len[e.v] = l;pre[e.v] = e;heapfy(idx[e.v]);}}private int poll(){int ret = hep[0];heapfy(swap(0,--sz));return ret;}private void heapfy(int k){int p = k -1 >>1;if (0 <= p && cmp.compare(len[hep[p]],len[hep[k]]) > 0) {heapfy(swap(p,k));return;}int c = k <<1 |1;if (sz <= c)return;if (c +1 < sz && cmp.compare(len[hep[c]],len[hep[c +1]]) > 0)c++;if (cmp.compare(len[hep[c]],len[hep[k]]) < 0)heapfy(swap(c,k));}private int swap(int i,int j){hep[i] ^= hep[j];hep[j] ^= hep[i];hep[i] ^= hep[j];idx[hep[i]] = i;idx[hep[j]] = j;return i;}}abstract class SparseTable{private int n;private long[] tbl;public SparseTable(int n){int K = max(1,32 -Integer.numberOfLeadingZeros(n -1));this.n = 1 <<K;tbl = new long[K *this.n];for (int i = 0;i < this.n;i++)tbl[i] = i < n ? init(i) : e();for (int k = 1;k < K;k++)for (int s = 1 <<k;s < this.n;s += 2 <<k) {int b = k *this.n;tbl[b +s] = s < n ? init(s) : e();tbl[b +s -1] = s < n ? init(s -1) : e();for (int i = 1;i < 1 <<k;i++) {tbl[b +s +i] = agg(tbl[b +s +i -1],tbl[s +i]);tbl[b +s -1 -i] = agg(tbl[b +s -i],tbl[s -1 -i]);}}}protected abstract long e();protected abstract long init(int i);protected abstract long agg(long a,long b);public long get(int l,int r){r--;if (l == r)return tbl[l];int k = 31 -Integer.numberOfLeadingZeros(l ^r);long ret = e();ret = agg(tbl[k *n +l],tbl[k *n +r]);return ret;}}class NTT{private static long[][] sum = sum();public static long[] convolution(long[] a,long[] b,int l){ return convolution(a,0,a.length,b,0,b.length,l); }public static long[] convolution(long[] a,long[] b){return convolution(a,0,a.length,b,0,b.length,a.length +b.length -1);}public static long[] convolution(long[] a,int al,int ar,long[] b,int bl,int br,int l){return copyOf(convolution(a,al,ar,b,bl,br),l);}public static long[] convolution(long[] a,int al,int ar,long[] b,int bl,int br){int n = ar -al;int m = br -bl;int z = max(1,Integer.highestOneBit(n +m -2) <<1);long[] ta = new long[z];long[] tb = new long[z];System.arraycopy(a,al,ta,0,ar -al);System.arraycopy(b,bl,tb,0,br -bl);a = ta;b = tb;butterfly(a,sum[0]);butterfly(b,sum[0]);for (int i = 0;i < z;i++)a[i] = a[i] *b[i] %998_244_353;butterflyInv(a,sum[1]);long iz = pow(z,998_244_351);for (int i = 0;i < a.length;i++)a[i] = a[i] *iz %998_244_353;return a;}private static void butterflyInv(long[] a,long[] sum){int n = a.length;int h = 32 -Integer.numberOfLeadingZeros(n -1);for (int ph = h;ph >= 1;ph--) {int w = 1 <<ph -1,p = 1 <<h -ph;long now = 1;for (int s = 0;s < w;s++) {int offset = s <<h -ph +1;for (int i = 0;i < p;i++) {long l = a[i +offset];long r = a[i +offset +p];a[i +offset] = (l +r) %998_244_353;a[i +offset +p] = (998_244_353 +l -r) *now %998_244_353;}int x = Integer.numberOfTrailingZeros(~s);now = now *sum[x] %998_244_353;}}}private static void butterfly(long[] a,long[] sum){int n = a.length;int h = 32 -Integer.numberOfLeadingZeros(n -1);long ADD = 998_244_351L *998_244_353;for (int ph = 1;ph <= h;ph++) {int w = 1 <<ph -1,p = 1 <<h -ph;long now = 1;for (int s = 0;s < w;s++) {int offset = s <<h -ph +1;for (int i = 0;i < p;i++) {long l = a[i +offset];long r = a[i +offset +p] *now;a[i +offset] = (l +r) %998_244_353;a[i +offset +p] = (l -r +ADD) %998_244_353;}int x = Integer.numberOfTrailingZeros(~s);now = now *sum[x] %998_244_353;}}}private static long[][] sum(){long[][] sum = new long[2][21];long[] es = new long[22];long[] ies = new long[22];long e = 15311432;long ie = 469870224;for (int i = 22;i-- > 0;) {es[i] = e;ies[i] = ie;e = e *e %998_244_353;ie = ie *ie %998_244_353;}long se = 1;long sie = 1;for (int i = 0;i < 21;i++) {sum[0][i] = es[i] *se %998_244_353;se = se *ies[i] %998_244_353;sum[1][i] = ies[i] *sie %998_244_353;sie = sie *es[i] %998_244_353;}return sum;}private static long pow(long x,long n){x %= 998_244_353;long ret = 1;do {if ((n &1) == 1)ret = ret *x %998_244_353;x = x *x %998_244_353;} while (0 < (n >>= 1));return ret;}}class PrefixSum{private long[] sum;private int i;public PrefixSum(int n){ sum = new long[n +1]; }public PrefixSum(long[] a){this(a.length);for (int i = 0;i < a.length;i++)sum[i +1] = sum[i] +a[i];}public void add(long a){ sum[i +1] = sum[i++] +a; }public long get(int l,int r){ return sum[r] -sum[l]; }public long get(int i){ return get(i,i +1); }}abstract class Trie<V> {private int b;public Node root;public Trie(){ this('z' +1); }public Trie(int b){this.b = b;root = new Node();}abstract V e();public MyList<Node> path(char[] s){MyList<Node> q = new MyList<>(s.length +1);var nd = root;q.add(nd);for (char c:s) {if (nd.ch[c] == null)nd.ch[c] = new Node();q.add(nd = nd.ch[c]);}return q;}class Node{private Node[] ch = Util.cast(Array.newInstance(this.getClass(),b));public V v = e();}}class LowLink extends Graph<Long>{private int[] low,ord,inc;public LowLink(int n){ super(n,false); }public void build(){low = new int[n];ord = new int[n];inc = new int[n];fill(ord,-1);Iterator<Edge<Long>>[] itr = Util.cast(new Iterator[n]);for (int v = 0;v < n;v++)itr[v] = go(v).iterator();int[] stk = new int[n +2];stk[0] = -1;for (int root = 0,s = 0,count = 0;root < n;root++) {if (ord[root] != -1)continue;ord[root] = low[root] = count++;inc[root]--;stk[s = 1] = root;while (0 < s) {int v = stk[s],p = stk[s -1];if (itr[v].hasNext()) {int w = itr[v].next().v;if (ord[w] == -1) {ord[w] = low[w] = count++;stk[++s] = w;} else if (w != p && low[v] > ord[w])low[v] = ord[w];} else {s--;if (p != -1) {if (low[p] > low[v])low[p] = low[v];if (ord[p] <= low[v])inc[p]++;}}}}}public boolean isBridge(int x,int y){ return ord[x] < low[y] || ord[y] < low[x]; }public boolean isArticulation(int x){ return inc[x] > 0; }public int articulationValue(int x){ return inc[x]; }}class Edge<L> {public int id,u,v;public L val;public Edge<L> re;public Edge(int id,int u,int v,L val){this.id = id;this.u = u;this.v = v;this.val = val;}}class Graph<L> {protected int n;protected MyList<Edge<L>> es;private MyList<Edge<L>>[] go,bk;public Graph(int n,boolean dir){this.n = n;go = Util.cast(new MyList[n]);bk = dir ? Util.cast(new MyList[n]) : go;for (int i = 0;i < n;i++) {go[i] = new MyList<>();bk[i] = new MyList<>();}es = new MyList<>();}public int size(){ return n; }protected L inv(L l){ return l; }public void addEdge(int u,int v){ addEdge(u,v,null); }public void addEdge(int u,int v,L l){var e = new Edge<>(es.size(),u,v,l);var re = new Edge<>(e.id,e.v,e.u,inv(e.val));es.add(e);go[u].add(re.re = e);bk[v].add(e.re = re);}public MyList<Edge<L>> go(int u){ return go[u]; }public MyList<Edge<L>> bk(int u){ return bk[u]; }}abstract class Sum3D{private long[] sum;private int w,d;public Sum3D(int h,int w,int d){this.w = w;this.d = d;sum = new long[(h +1) *(w +1) *(d +1)];for (int i = 0;i < h;i++)for (int j = 0;j < w;j++)for (int k = 0;k < d;k++)sum[top(i +1,j +1,k +1)] = a(i,j,k)+sum[top(i,j +1,k +1)] +sum[top(i +1,j,k +1)] +sum[top(i +1,j +1,k)]-sum[top(i +1,j,k)] -sum[top(i,j +1,k)] -sum[top(i,j,k +1)]+sum[top(i,j,k)];}abstract long a(int i,int j,int k);private int top(int i,int j,int k){ return i *(w +1) *(d +1) +j *(d +1) +k; }long get(int il,int ir,int jl,int jr,int kl,int kr){return sum[top(ir,jr,kr)]-sum[top(il,jr,kr)] -sum[top(ir,jl,kr)] -sum[top(ir,jr,kl)]+sum[top(ir,jl,kl)] +sum[top(il,jr,kl)] +sum[top(il,jl,kr)]-sum[top(il,jl,kl)];}}abstract class BaseV{public int sz;public boolean fail;}class MyStack<T> extends MyList<T>{public T pop(){ return remove(size() -1); }public T peek(){ return get(size() -1); }}class MyList<T> implements Iterable<T>{private T[] arr;private int sz;public MyList(){ this(16); }public MyList(int n){ arr = Util.cast(new Object[max(16,n)]); }public MyList(MyList<T> org){this(org.sz);System.arraycopy(org.arr,0,arr,0,sz = org.sz);}public boolean isEmpty(){ return sz == 0; }public int size(){ return sz; }public T get(int i){ return arr[i]; }public T last(){ return sz == 0 ? null : arr[sz -1]; }public void add(T t){ (arr = sz < arr.length ? arr : copyOf(arr,sz *5 >>2))[sz++] = t; }public void addAll(MyList<T> list){for (var t:list)add(t);}public T remove(int i){var ret = arr[i];sz--;for (int j = i;j < sz;j++)arr[j] = arr[j +1];return ret;}public T removeFast(int i){var ret = arr[i];arr[i] = arr[--sz];return ret;}public void sort(){ sort(Util.cast(Comparator.naturalOrder())); }public void sort(Comparator<T> cmp){ Arrays.sort(arr,0,sz,cmp); }public <U> MyList<U> map(Function<T, U> func){MyList<U> ret = new MyList<>(sz);forEach(t -> ret.add(func.apply(t)));return ret;}public MyList<T> rev(){MyList<T> ret = new MyList<>(sz);for (int i = sz;i-- > 0;)ret.add(get(i));return ret;}public T[] toArray(){if (sz == 0)return Util.cast(new Object[0]);T[] ret = Util.cast(Array.newInstance(arr[0].getClass(),sz));System.arraycopy(arr,0,ret,0,sz);return ret;}public void swap(int i,int j){var t = arr[i];arr[i] = arr[j];arr[j] = t;}public void set(int i,T t){ arr[i] = t; }public void clear(){ sz = 0; }@Overridepublic Iterator<T> iterator(){return new Iterator<>(){int i = 0;@Overridepublic boolean hasNext(){ return i < sz; }@Overridepublic T next(){ return arr[i++]; }};}}class BaseSolver extends Util{public MyReader in;public MyWriter out,log;public BaseSolver(MyReader in,MyWriter out,MyWriter log){this.in = in;this.out = out;this.log = log;}public int[][] addId(int[][] T){return arr(new int[T.length][],i -> {int[] t = copyOf(T[i],T[i].length +1);t[t.length -1] = i;return t;});}public long inv(long x){ return pow(x,mod -2); }public long inv(long x,long mod){ return (extendGcd(x,mod)[0] +mod) %mod; }public long pow(long x,long n){ return pow(x,n,Util.mod); }public long pow(long x,long n,long mod){long ret = 1;for (x %= mod;0 < n;x = x *x %mod,n >>= 1)if ((n &1) == 1)ret = ret *x %mod;return ret;}public int bSearchI(int o,int n,IntPredicate judge){for (int m = 0;1 < abs(n -o);)m = judge.test(m = o +n >>1) ? (o = m) : (n = m);return o;}public long bSearchL(long o,long n,LongPredicate judge){for (long m = 0;1 < abs(n -o);)m = judge.test(m = o +n >>1) ? (o = m) : (n = m);return o;}public double bSearchD(double o,double n,DoublePredicate judge){for (double m,c = 0;c < 100;c++)m = judge.test(m = (o +n) /2) ? (o = m) : (n = m);return o;}public long gcd(long a,long b){while (0 < b) {long t = a;a = b;b = t %b;}return a;}public long[] extendGcd(long a,long b){long x0 = 1,y0 = 0,x1 = 0,y1 = 1;while (b != 0) {long q = a /b,t = a %b,tx = x1,ty = y1;a = b;b = t;x1 = x0 -q *x1;y1 = y0 -q *y1;x0 = tx;y0 = ty;}return new long[]{x0, y0, a};}public long lcm(long a,long b){ return b /gcd(a,b) *a; }public long ceil(long a,long b){ return (a +b -1) /b; }public int lis(int[] arr){int[] lis = new int[arr.length];fill(lis,infI);for (var a:arr) {int i = bSearchI(0,arr.length,ii -> lis[ii] < a) +1;lis[i] = a;}return bSearchI(0,arr.length,i -> lis[i] < infI) +1;}}class Util{public static String yes = "Yes",no = "No";public static int infI = (1 <<30) -1;public static long infL = (1L <<61 |1 <<30) -1,mod = 998244353;public static Random rd = ThreadLocalRandom.current();private long st = System.currentTimeMillis();protected long elapsed(){ return System.currentTimeMillis() -st; }protected void reset(){ st = System.currentTimeMillis(); }public static int[] arrI(int N,IntUnaryOperator f){int[] ret = new int[N];setAll(ret,f);return ret;}public static long[] arrL(int N,IntToLongFunction f){long[] ret = new long[N];setAll(ret,f);return ret;}public static double[] arrD(int N,IntToDoubleFunction f){double[] ret = new double[N];setAll(ret,f);return ret;}public static <T> T[] arr(T[] arr,IntFunction<T> f){setAll(arr,f);return arr;}@SuppressWarnings("unchecked")public static <T> T cast(Object obj){ return (T) obj; }}class MyReader{private byte[] buf = new byte[1 <<16];private int ptr,tail;private InputStream in;public MyReader(InputStream in){ this.in = in; }private byte read(){if (ptr == tail)try {tail = in.read(buf);ptr = 0;} catch (IOException e) {}return buf[ptr++];}private boolean isPrintable(byte c){ return 32 < c && c < 127; }private byte nextPrintable(){byte ret = read();while (!isPrintable(ret))ret = read();return ret;}public int it(){ return toIntExact(lg()); }public int[] it(int N){ return Util.arrI(N,i -> it()); }public int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }public int idx(){ return it() -1; }public int[] idx(int N){ return Util.arrI(N,i -> idx()); }public int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }public long lg(){byte i = nextPrintable();boolean negative = i == 45;long n = negative ? 0 : i -'0';while (isPrintable(i = read()))n = 10 *n +i -'0';return negative ? -n : n;}public long[] lg(int N){ return Util.arrL(N,i -> lg()); }public long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }public double dbl(){String str = str();return Double.parseDouble(str);}public double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }public double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }public char[] ch(){ return str().toCharArray(); }public char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }public String line(){StringBuilder sb = new StringBuilder();for (byte c;(c = read()) != '\n';)sb.append((char) c);return sb.toString();}public String str(){StringBuilder sb = new StringBuilder();sb.append((char) nextPrintable());for (byte c;isPrintable(c = read());)sb.append((char) c);return sb.toString();}public String[] str(int N){ return Util.arr(new String[N],i -> str()); }public String[][] str(int H,int W){ return Util.arr(new String[H][],i -> str(W)); }}class MyWriter{private OutputStream out;private byte[] buf = new byte[1 <<16],ibuf = new byte[20];private int tail;private boolean autoflush;public MyWriter(OutputStream out,boolean autoflush){this.out = out;this.autoflush = autoflush;}public void flush(){try {out.write(buf,0,tail);tail = 0;} catch (IOException e) {e.printStackTrace();}}private void write(byte b){buf[tail++] = b;if (tail == buf.length)flush();}private void write(long n){if (n < 0) {n = -n;write((byte) '-');}int i = ibuf.length;do {ibuf[--i] = (byte) (n %10 +'0');n /= 10;} while (n > 0);while (i < ibuf.length)write(ibuf[i++]);}private void print(Object obj){if (obj instanceof Boolean)print((boolean) obj ? Util.yes : Util.no);else if (obj instanceof Integer)write((int) obj);else if (obj instanceof Long)write((long) obj);else if (obj instanceof char[])for (char b:(char[]) obj)write((byte) b);else if (obj.getClass().isArray()) {int l = Array.getLength(obj);for (int i = 0;i < l;i++) {print(Array.get(obj,i));if (i +1 < l)write((byte) ' ');}} elseprint(Objects.toString(obj).toCharArray());}public void println(Object obj){if (obj == null)obj = "null";if (obj instanceof Iterable<?>)for (Object e:(Iterable<?>) obj)println(e);else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) {int l = Array.getLength(obj);for (int i = 0;i < l;i++)println(Array.get(obj,i));} else {print(obj);write((byte) '\n');if (autoflush)flush();}}public void printlns(Object... obj){print(obj);write((byte) '\n');if (autoflush)flush();}}