結果
問題 | No.2857 Div Array |
ユーザー |
|
提出日時 | 2024-08-25 16:15:51 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 230 ms / 2,000 ms |
コード長 | 28,642 bytes |
コンパイル時間 | 4,402 ms |
コンパイル使用メモリ | 100,008 KB |
実行使用メモリ | 54,476 KB |
最終ジャッジ日時 | 2024-08-25 16:16:03 |
合計ジャッジ時間 | 8,538 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
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 M = in.it();int K = in.it();TreeMap<Integer, Integer> mp = new TreeMap<>();for (int m = 1;m <= M;m++)mp.merge(M /m,1,Integer::sum);int[][] map = new int[mp.size()][2];for (int i = 0;i < map.length;i++) {var e = mp.pollFirstEntry();map[i][0] = e.getKey();map[i][1] = e.getValue();}long[] A = Util.arrL(map.length,i -> map[i][1]);long[][] X = new long[map.length][map.length];for (int i = 0;i < map.length;i++)for (int j = 0;j < map.length;j++)if (abs(map[i][0] -map[j][0]) <= K)X[i][j] += map[j][1];long ans = 0;for (var v:Matrix.mul(A,Matrix.pow(X,N -1)))ans += v;return ans %mod;// int N = in.it();// int K = in.it();// int X = in.it();// long[] H = in.lg(N);//// Set<Long> set0 = new HashSet<>();// Set<Long> set = new HashSet<>();// for (var h:H) {// set0.add(h);// set.add(h %X);// }// if (set0.size() == 1)// return true;// if (set.size() > 1)// return false;//// long mm = infL;// for (int i = 0;i < K;i++)// if (H[i] > (mm = min(mm,H[i])))// return false;//// mm = infL;// for (int i = N -1;i >= N -K;i--)// if (H[i] > (mm = min(mm,H[i])))// return false;//// // for (int i = 0;i +K <= N;i++)// // while (H[i] < 4)// // for (int j = 0;j < K;j++)// // H[i +j] += X;//// long[] sum = new long[K];// int[] cnt = new int[K];//// for (int i = 0;i < N;i++) {// sum[i %K] += H[i];// cnt[i %K]++;// }//// if (N %K == 0) {// Set<Long> set2 = new HashSet<>();// for (var s:sum)// set2.add(s);// return set2.size() == 1;// }//// long m = infL;// long M = -infL;// for (int i = 0;i < K;i++) {// m = min(m,sum[i]);// M = max(M,sum[i]);// }//// long mok = M -m;// DualBIT bit = new DualBIT(N);// for (int i = 0;i < N;i++)// bit.upd(i,i +1,H[i]);//// for (int i = 0;i +K <= N;i++) {// long d = mok -bit.get(i);// if (d %X != 0)// return false;// bit.upd(i,i +K,d);// }//// Set<Long> set2 = new HashSet<>();// for (int i = 0;i < N;i++)// set2.add(bit.get(i));//// return set2.size() == 1;}private void tmp(int N,int K,int X,long[] H){long[] cnt = new long[N];long mok = H[0] %X +X *10;DualBIT bit = new DualBIT(N);for (int i = 0;i < N;i++)bit.upd(i,i +1,H[i]);for (int i = 0;i +K <= N;i++) {long d = mok -bit.get(i);if (d %X != 0)throw new RuntimeException();cnt[i] = d;bit.upd(i,i +K,d);}long[] arr = new long[N];for (int i = 0;i < N;i++)arr[i] = bit.get(i);log.println(arr);log.println(cnt);}<T extends BaseV> void log(Seg<T, ?> seg,int n){T[] a = (T[]) new BaseV[n];for (int i = 0;i < n;i++)a[i] = seg.get(i);log.println(a);}private int[] zaatu(int[][] T){List<Integer> list = new ArrayList<>();list.add(0);for (var t:T)list.add(t[1]);Set<Integer> set = new TreeSet<>(list);Map<Integer, Integer> map = new HashMap<>();int[] ret = new int[set.size()];for (var s:set) {ret[map.size()] = s;map.put(s,map.size());}for (var t:T)t[1] = map.get(t[1]);return ret;}private int calc(String s){var rh = new RollingHash(s.toCharArray(),false);int ret = 1;for (int i = 0;i < s.length();i++) {int l = (ret -1) /2;while (0 <= i -(l +1) && i +l +2 <= s.length() && rh.get(i -(l +1),i) == rh.get(i +l +2,i +1))l++;ret = max(ret,l *2 +1);l = ret /2;while (0 <= i -l && i +l +2 <= s.length() && rh.get(i -l,i +1) == rh.get(i +l +2,i +1))l++;ret = max(ret,l *2);}return ret;}int[][] trans(int[]... T){ return Util.arr(new int[T[0].length][],i -> Util.arrI(T.length,j -> T[j][i])); }// void add(SegmentTree<Data, Long> seg,int a,long[] map){ seg.upd(a,map[a]); }//// void rem(SegmentTree<Data, Long> seg,int a,long[] map){ seg.upd(a,-map[a]); }//// long[] mo(int N,int[] A,int[][] T,long[] map,SegmentTree<Data, Long> seg,long[] ans){// int k = 32 -Integer.numberOfLeadingZeros((int) (Math.sqrt(1.5 /T.length) *N) +1);// sort(T,(a,b) -> (a[0] >>k != b[0] >>k ? a[0] -b[0] : (a[0] >>k &1) == 1 ? a[1] -b[1] : b[1] -a[1]));// int l = T[0][0];// int r = l -1;// for (var t:T) {// while (t[0] < l)// add(seg,A[--l],map);// while (r < t[1])// add(seg,A[++r],map);// while (l < t[0])// rem(seg,A[l++],map);// while (t[1] < r)// rem(seg,A[r--],map);// ans[t[2]] = seg.get(0,100_000 +1).v;// }// return ans;// }}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;}}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); }}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);}}class RollingHash{private static long MOD = (1L <<61) -1,MASK30 = (1L <<30) -1,MASK31 = (1L <<31) -1,base = ThreadLocalRandom.current().nextLong(Util.infI,MOD);private static long[] pow = {1};int n;private long[] hash,S;private boolean updatable;private RollingHash rev;public RollingHash(char[] S,boolean updatable){ this(Util.arrL(S.length,i -> S[i]),updatable); }public RollingHash(int[] S,boolean updatable){ this(Util.arrL(S.length,i -> S[i]),updatable); }public RollingHash(long[] S,boolean updatable){this.S = new long[n = S.length];this.updatable = updatable;hash = new long[n +1];if (pow.length <= n) {int s = pow.length;pow = copyOf(pow,max(pow.length <<1,n +1));for (int i = s;i < pow.length;i++)pow[i] = mul(pow[i -1],base);}for (int i = 0;i < n;i++)set(i,S[i]);}public long get(int i){ return get(i,i +1); }public long get(int l,int r){if (l > r)return (rev == null ? rev = rev() : rev).get(n -l,n -r);return mod(hash(r) -mul(hash(l),pow[r -l]));}public void upd(int i,long v){assert updatable;set(i,v);if (rev != null)rev.set(n -i -1,v);}private void set(int i,long v){if (updatable)for (int x = i +1;x <= n;x += x &-x)hash[x] = mod(hash[x] +mul(v -S[i],pow[x -i -1]));elsehash[i +1] = mod(mul(hash[i],base) +v);S[i] = v;}private long hash(int i){long ret = 0;if (updatable)for (int x = i;x > 0;x -= x &-x)ret = mod(ret +mul(hash[x],pow[i -x]));elseret = hash[i];return ret;}private RollingHash rev(){long[] s = new long[n];for (int i = 0;i < n;i++)s[i] = S[n -1 -i];return new RollingHash(s,updatable);}private static long mul(long a,long b){long au = a >>31;long ad = a &MASK31;long bu = b >>31;long bd = b &MASK31;long mid = ad *bu +au *bd;return mod((au *bu <<1) +(mid >>30) +((mid &MASK30) <<31) +ad *bd);}private static long mod(long val){return val < 0 ? val +MOD : (val = (val &MOD) +(val >>61)) < MOD ? val : val -MOD;}}class Matrix{public static long[] mul(long[] a,long[][] b){assert a.length == b.length;int H = b[0].length,W = a.length;long[] ret = new long[H];for (int i = 0;i < H;i++)for (int j = 0;j < W;j++)ret[i] = (ret[i] +a[j] *b[j][i]) %Util.mod;return ret;}public static long[][] mul(long[][] a,long[][] b){assert a[0].length == b.length;int H = a.length,W = b[0].length,Z = b.length;long[][] ret = new long[H][W];for (int z = 0;z < Z;z++)for (int i = 0;i < H;i++)for (int j = 0;j < W;j++)ret[i][j] = (ret[i][j] +a[i][z] *b[z][j]) %Util.mod;return ret;}public static long[][] pow(long[][] x,long n){long[][] ret = new long[x.length][x.length];for (int i = 0;i < x.length;i++)ret[i][i] = 1;for (;0 < n;x = (n >>= 1) > 0 ? mul(x,x) : x)if ((n &1) == 1)ret = mul(ret,x);return ret;}}class Grid{private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};private int H,W;public Grid(int H,int W){this.H = H;this.W = W;}public int[] sur(int p){MyList<int[]> tmp = sur(toi(p),toj(p));int[] ret = new int[tmp.size()];for (int i = 0;i < tmp.size();i++)ret[i] = top(tmp.get(i)[0],tmp.get(i)[1]);return ret;}public MyList<int[]> sur(int i,int j){MyList<int[]> ret = new MyList<>();for (var d:dirs) {int ni = i +d[0];int nj = j +d[1];if (valid(ni,H) && valid(nj,W))ret.add(new int[]{ni, nj});}return ret;}private boolean valid(int i,int N){ return 0 <= i && i < N; }public int top(int i,int j){ return i *W +j; }public int toi(int p){ return p /W; }public int toj(int p){ return p %W; }}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); }}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> {public int n;public 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<>();}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]; }}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 MySet implements Iterable<Integer>{private Set<Integer> set;private BitSet bit;public MySet(){ set = new HashSet<>(); }public int size(){ return set != null ? set.size() : bit.cardinality(); }public void add(int x){if (set != null) {set.add(x);if (set.size() == 100) {bit = new BitSet();for (int i:set)bit.set(i);set = null;}} elsebit.set(x);}public boolean contains(int x){ return set == null ? bit.get(x) : set.contains(x); }@Overridepublic Iterator<Integer> iterator(){return set != null ? set.iterator() : new Iterator<>(){int w = bit.nextSetBit(0);@Overridepublic Integer next(){int ret = w;w = bit.nextSetBit(w +1);return ret;}@Overridepublic boolean hasNext(){ return w != -1; }};}}class Data extends BaseV{long v;public Data(long v){ this.v = v; }@Overridepublic String toString(){ return v +""; }}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)];}}class RangeSet{private TreeSet<long[]> set;public RangeSet(){set = new TreeSet<>(Comparator.comparing(t -> t[0]));long inf = Util.infL;set.add(new long[]{-inf, -inf});set.add(new long[]{inf, inf});}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);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);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];}public long[][] toArray(){long[][] ret = new long[set.size() -2][];long[] x = {set.first()[0]};for (int i = 0;i < ret.length;i++)x[0] = (ret[i] = set.higher(x))[0];return ret;}public long cardinality(long l,long r){long ret = 0;long[] key = {r};while (l < r) {var t = set.lower(key);if (t[1] <= l)break;ret += min(r,t[1]) -max(l,t[0]);key = t;}return ret;}public long first(){ return set.higher(new long[]{-Util.infL})[0]; }}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 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 < 200;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(){ 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 ln(){write((byte) '\n');if (autoflush)flush();}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);ln();}}public void printlns(Object... o){print(o);ln();}}