B - Greater Than Average
Source: atcoder
Difficulty: 500

Problem Statement
Define the
score
of a non-empty integer sequence
x = (x_1, \ldots, x_n)
as the number of elements of
x
that are strictly greater than the average of
x
.
That is, the score of
x
is the count of indices
i
satisfying
x_i > \dfrac{x_1+\cdots+x_n}{n}
.
You are given a length-
N
integer sequence
A = (A_1, \ldots, A_N)
. Find the maximum score of a non-empty subsequence of
A
.
There are
T
test cases; solve each one.
Definition of subsequence
A subsequence of
A
is any sequence obtained by deleting zero or more elements from
A
and keeping the remaining elements in their original order.
Constraints
1\le T\le 2\times 10^5
2\le N\le 2\times 10^5
1\le A_i\le 10^9
All input values are integers.
The sum of
N
over all test cases is at most
2\times 10^5
.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T
Each case is given in the following format:
N
A_1
\cdots
A_N
Output
Print
T
lines. The
i
-th line should contain the maximum score of a non-empty subsequence of
A
for the
i
-th test case.
Sample Input 1
3
5
2 6 5 7 5
5
10 10 10 10 10
5
1 10 100 1000 10000
Sample Output 1
3
0
1
For the first test case, below are examples of subsequences, their averages, and their scores.
x = (A_1) = (2)
: the average is
2
, and the score is
0
.
x = (A_3,A_5) = (5,5)
: the average is
5
, and the score is
0
.
x = (A_1,A_3,A_4,A_5) = (2,5,7,5)
: the average is
\frac{19}{4}
, and the score is
3
.
x = (A_1,A_2,A_3,A_4,A_5) = (2,6,5,7,5)
: the average is
5
, and the score is
2
.

C++ solution:
#include <iostream>
#include <algorithm>
using namespace std;

void solve() {
	int n;
	cin >> n;
	static int a[200000];
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a, a + n);
	int answer = 0;
	long long sum = 0;
	int j = 0;
	for (int i = 0; i < n; ++i) {
		sum += a[i];
		while (j < i && (long long)a[j + 1] * (i + 1) <= sum) {
			++j;
		}
		answer = max(answer, i - j);
	}
	cout << answer << '\n';
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		solve();
	}
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

func main() {
	t := getI()
	for i := 0; i < t; i++ {
		n := getI()
		A := getInts(n)
		sort.Ints(A)
		ans := 0
		sum := 0
		for j := 0; j < n; j++ {
			sum += A[j]
			// j*A[k] > sum となるような 0 <= k <= j のupper boundを求める
			l, r := 0, j
			for l < r {
				m := (l + r) / 2
				if A[m]*(j+1) > sum {
					r = m
				} else {
					l = m + 1
				}
			}
			if l <= j {
				if A[l]*(j+1) <= sum {
					l++
				}
			}
			ans = max(ans, j-l+1)
		}
		out(ans)
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)
}

func out(x ...interface{}) {
	fmt.Println(x...)
}

func outSlice[T any](s []T) {
	for i := 0; i < len(s)-1; i++ {
		fmt.Print(s[i], " ")
	}
	fmt.Println(s[len(s)-1])
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

Java solution:
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.List;
import java.util.function.*;
import java.io.*;
import java.util.stream.*;

public class Main {
    static int dist2(int dx,int dy){return dx*dx+dy*dy;}
    static long dist2(long dx,long dy){return dx*dx+dy*dy;}

    static double min(double... a){
        double res=Double.POSITIVE_INFINITY;
        for(double v:a){res=Double.min(v,res);}
        return res;
    }
    static float min(float... a){
        float res=Float.POSITIVE_INFINITY;
        for(float v:a){res=Float.min(v,res);}
        return res;
    }
    static int min(int... a){
        int res=Integer.MAX_VALUE;
        for(int v:a){res=Integer.min(v,res);}
        return res;
    }
    static long min(long... a){
        long res=Long.MAX_VALUE;
        for(long v:a){res=Long.min(v,res);}
        return res;
    }
    static double max(double... a){
        double res=Double.NEGATIVE_INFINITY;
        for(double v:a){res=Double.max(v,res);}
        return res;
    }
    static float max(float... a){
        float res=Float.NEGATIVE_INFINITY;
        for(float v:a){res=Float.max(v,res);}
        return res;
    }
    static int max(int... a){
        int res=Integer.MIN_VALUE;
        for(int v:a){res=Integer.max(v,res);}
        return res;
    }
    static long max(long... a){
        long res=Long.MIN_VALUE;
        for(long v:a){res=Long.max(v,res);}
        return res;
    }

    static class Ratio extends Number implements Comparable<Ratio>{
        //static Ratio ZERO=new Ratio(0L,1L);
        //static Ratio ONE=new Ratio(1L,1L);
        final long si;
        final long bo;
        Ratio(long v){si=v;bo=1L;}
        Ratio(long si,long bo){
            //if(bo==0L){throw new ArithmeticException("divide dy zero.");}
            long gcd=gcd(si,bo);
            si=si/gcd;
            bo=bo/gcd;
            if(bo>0){
                this.si=si;
                this.bo=bo;
            }else{
                this.si=-si;
                this.bo=-bo;
            }
        }
        Ratio add(Ratio o){
            // a/b + c/d = ad/bd + cb/db = (ad+bc) / bd
            return new Ratio((si*o.bo+o.si*bo),bo*o.bo);
        }
        Ratio sub(Ratio o){
            // a/b - c/d = ad/bd - cb/db = (ad-bc) / bd
            return new Ratio((si*o.bo-o.si*bo),bo*o.bo);
        }
        Ratio mul(Ratio o){
            // a/b * c/d = (a*c) / (b*d)
            long gcd1=gcd(si  ,o.bo);
            long gcd2=gcd(o.si,  bo);
            return new Ratio(si/gcd1*o.si/gcd2,bo/gcd2*o.bo/gcd1);
        }
        Ratio div(Ratio o){
            if(o.si==0L){throw new ArithmeticException("divide dy zero.");}
            // a/b * d/c =  = (a*d) / (b*c)
            long gcd1=gcd(si  ,o.si);
            long gcd2=gcd(o.bo,  bo);
            return new Ratio(si/gcd1*o.bo/gcd2,bo/gcd2*o.si/gcd1);
        }
        //Number
        public double doubleValue(){
            return 1.0*si/bo;
        }
        public float floatValue(){
            return 1f*si/bo;
        }
        public int intValue(){
            return (int)longValue();
        }
        public long longValue(){
            return si/bo;
        }
        //Comparable
        public int compareTo(Ratio o){
            return Long.compare(si*o.bo,o.si*bo);
        }
        public static int compare(Ratio r1,Ratio r2){return r1.compareTo(r2);}
        //Object
        public boolean equals(Object o){
            if(this==o){return true;}
            if(!(o instanceof Ratio ro)){return false;}
            return si==ro.si&&bo==ro.bo;
        }
        public int hashCode(){
            return Long.hashCode(si)*31+Long.hashCode(bo);
        }
        public String toString(){
            return si+"/"+bo;
        }
    }
    static class Pair<T,U>{
        T first;U second;
        Pair(T f,U s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            return Objects.equals(first, pair.first) && Objects.equals(second, pair.second);
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first.toString()+","+second.toString()+")";}
    }
    static class Pairint<T>{
        int first;T second;
        Pairint(int f,T s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairint<?> pair = (Pairint<?>) o;
            return Objects.equals(first, pair.first) && Objects.equals(second, pair.second);
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second.toString()+")";}
    }
    static class Pairintint{
        int first;int second;
        Pairintint(int f, int s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairintint that = (Pairintint) o;
            return first == that.first && second == that.second;
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second+")";}
        public static Comparator<Pairintint> henkaku(){
            return (o1, o2) -> {
                int s = o1.second > 0 ? 1 :
                        o1.second < 0 ? 2 :
                                o1.first > 0 ? 1 :
                                        o1.first < 0 ? 2 : 0;
                int t = o2.second > 0 ? 1 :
                        o2.second < 0 ? 2 :
                                o2.first > 0 ? 1 :
                                        o2.first < 0 ? 2 : 0;
                if (s != t) { return Integer.compare(s, t); }
                return Long.compare(o2.first * (long) o1.second, o1.first * (long) o2.second);
            };
        }
    }
    static class Pairintlong{
        int first;long second;
        Pairintlong(int f, long s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairintlong that = (Pairintlong) o;
            return first == that.first && second == that.second;
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second+")";}
    }
    static class Pairintdouble{
        int first;double second;
        Pairintdouble(int f, double s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairintdouble that = (Pairintdouble) o;
            return first == that.first && second == that.second;
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second+")";}
    }
    static class Pairlong<T>{
        long first;T second;
        Pairlong(long f,T s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairlong<?> pair = (Pairlong<?>) o;
            return Objects.equals(first, pair.first) && Objects.equals(second, pair.second);
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second.toString()+")";}
    }
    static class Pairlonglong{
        long first;long second;
        Pairlonglong(long f, long s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairlonglong that = (Pairlonglong) o;
            return first == that.first && second == that.second;
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second+")";}
        public static Comparator<Pairlonglong> henkaku(){
            return (o1, o2) -> {
                int s = o1.second > 0L ? 1 :
                        o1.second < 0L ? 2 :
                                o1.first > 0L ? 1 :
                                        o1.first < 0L ? 2 : 0;
                int t = o2.second > 0L ? 1 :
                        o2.second < 0L ? 2 :
                                o2.first > 0L ? 1 :
                                        o2.first < 0L ? 2 : 0;
                if (s != t) { return Integer.compare(s, t); }
                //オーバーフローが嫌だからなるべく減らすべふgcdで割る 安全な確証があれば不要
                long gcd1=gcd(o1.first,o1.second);
                long gcd2=gcd(o2.first,o2.second);
                return Long.compare((o2.first/gcd2) * (o1.second/gcd1), (o1.first/gcd1) * (o2.second/gcd2));
            };
        }
    }
    static class Pairlongdouble{
        long first;double second;
        Pairlongdouble(long f, double s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairlongdouble that = (Pairlongdouble) o;
            return first == that.first && second == that.second;
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second+")";}
    }
    static class Pairdouble<T>{
        double first;T second;
        Pairdouble(long f,T s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairdouble<?> pair = (Pairdouble<?>) o;
            return Objects.equals(first, pair.first) && Objects.equals(second, pair.second);
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second.toString()+")";}
    }
    static class Pairdoubledouble{
        double first;double second;
        Pairdoubledouble(double f, double s){first=f;second=s;}
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pairdoubledouble that = (Pairdoubledouble) o;
            return first == that.first && second == that.second;
        }
        public int hashCode() {return Objects.hash(first, second);}
        public String toString(){return "("+first+","+second+")";}
        public static Comparator<Pairdoubledouble> henkaku(){
            return (o1, o2) -> {
                int s = o1.second > 0L ? 1 :
                        o1.second < 0L ? 2 :
                                o1.first > 0L ? 1 :
                                        o1.first < 0L ? 2 : 0;
                int t = o2.second > 0L ? 1 :
                        o2.second < 0L ? 2 :
                                o2.first > 0L ? 1 :
                                        o2.first < 0L ? 2 : 0;
                if (s != t) { return Integer.compare(s, t); }
                return Double.compare(o2.first*o1.second, o1.first*o2.second);
            };
        }
    }
    static int manhattan(Pairintint p1,Pairintint p2){
        return Math.abs(p2.first-p1.first)+Math.abs(p2.second-p1.second);
    }

    static boolean testbit(long bit,int i){return ((bit>>>i)&1)==1;}
    /**
     * 二分探索
     * @param a インデックスを要素にする関数 x->a[x]
     * @param ng 要素がngなインデックス -1
     * @param ok 要素がokなインデックス a.length
     * @param isOk 要素がokである条件 v->v>=k
     * @param mid 探索範囲の中間 (ng,ok)->(ng+ok)/2
     * @param isEnd 探索終了条件 (ng,ok)->Math.abs(ok-ng)<=1)
     * @return ok
     * @param <T> 要素の型
     * @param <U> インデックスの型
     */
    static <T ,U extends Number> U bs(Function<U, T> a, U ng, U ok, Predicate<T> isOk, BinaryOperator<U> mid, BiPredicate<U,U> isEnd){
        while(!isEnd.test(ng,ok)){
            U m=mid.apply(ng,ok);
            T am=a.apply(m);
            if(isOk.test(am)){
                ok=m;
            }else{
                ng=m;
            }
        }
        return ok;
    }
    /**
     * 二分探索
     * @param a インデックスを要素にする関数 x->a[x]
     * @param ngok 探索範囲 結果はこれを変更することで返す
     * @param isOk 要素がokである条件 v->v>=k
     * @param mid 探索範囲の中間 (ng,ok)->(ng+ok)/2
     * @param isEnd 探索終了条件 (ng,ok)->Math.abs(ok-ng)<=1)
     * @param <T> 要素の型
     * @param <U> インデックスの型
     */
    static <T ,U extends Number> void bs(Function<U, T> a, U[] ngok, Predicate<T> isOk, BinaryOperator<U> mid, BiPredicate<U,U> isEnd){
        while(!isEnd.test(ngok[0],ngok[1])){
            U m=mid.apply(ngok[0],ngok[1]);
            T am=a.apply(m);
            if(isOk.test(am)){
                ngok[1]=m;
            }else{
                ngok[0]=m;
            }
        }
    }

    static int repow(int b,int p) {
        long a = b;
        long res = 1;
        while (p > 0) {
            if (p % 2 == 1) {
                res *= a;
            }
            a *= a;
            p /= 2;
        }
        return (int) res;
    }
    static int repow(int b,int p, int m) {
        long a = b % m;
        long res = 1;
        while (p > 0) {
            if (p % 2 == 1) {
                res = (res * a) % m;
            }
            a = (a * a) % m;
            p /= 2;
        }
        return (int) res;
    }
    static long repow(long b,long p) {
        long a = b;
        long res = 1;
        while (p > 0) {
            if (p % 2 == 1) {
                res *= a;
            }
            a *= a;
            p /= 2;
        }
        return res;
    }
    static long repow(long b,long p,long m) {
        long a = b % m;
        long res = 1;
        while (p > 0) {
            if (p % 2 == 1) {
                res = (res * a) % m;
            }
            a = (a * a) % m;
            p /= 2;
        }
        return res;
    }
    static double repow(double b,long p) {
        double a = b;
        double res = 1.0;
        while (p > 0) {
            if (p % 2 == 1) {
                res *= a;
            }
            a *= a;
            p /= 2;
        }
        return res;
    }

    static int gcd(int a,int b){
        if (a==0||b==0) {return a+b;}
        a=Math.abs(a);b=Math.abs(b);
        while(true){
            int f=a%b;
            if(f==0){return b;}
            a=b;
            b=f;
        }
    }
    static long gcd(long a,long b) {
        a=Math.abs(a);
        b=Math.abs(b);
        if (a==0||b==0) {return a+b;}
        while(true){
            long f=a%b;
            if (f==0) {return b;}
            a=b;
            b=f;
        }
    }
    static int lcm(int a,int b){return a/gcd(a,b)*b;}
    static long lcm(long a,long b){return a/gcd(a,b)*b;}

    /**
     * gcd(a,b)と、ax+by=gcd(a,b)となるxとyを返す。
     * @param a 整数
     * @param b 整数
     * @return {gcd(a,b),x,y}
     */
    static long[] exeuc(long a, long b) {
        long rmm=a;long rm=b;long r;
        long xmm=1;long xm=0;long x;
        long ymm=0;long ym=1;long y;
        while(rm!=0){
            long q=rmm/rm;
            r=rmm-rm*q;x=xmm-xm*q;y=ymm-ym*q;
            //System.out.println(a*x+b*y+"="+r);
            rmm=rm;rm=r;xmm=xm;xm=x;ymm=ym;ym=y;
        }
        return new long[]{rmm, xmm, ymm};
    }
    static BigInteger[] exeuc(BigInteger a, BigInteger b) {
        BigInteger rmm=a;
        BigInteger rm=b;
        BigInteger r;
        BigInteger xmm=BigInteger.ONE;
        BigInteger xm=BigInteger.ZERO;
        BigInteger x;
        BigInteger ymm=BigInteger.ZERO;
        BigInteger ym=BigInteger.ONE;
        BigInteger y;
        while(!rm.equals(BigInteger.ZERO)){
            BigInteger q=rmm.divide(rm);
            r=rmm.subtract(rm.multiply(q));
            x=xmm.subtract(xm.multiply(q));
            y=ymm.subtract(ym.multiply(q));
            //System.out.println(a*x+b*y+"="+r);
            rmm=rm;rm=r;xmm=xm;xm=x;ymm=ym;ym=y;
        }
        return new BigInteger[]{rmm, xmm, ymm};
    }

    /**
     * 中国剰余定理 を解く
     * @param rm1 rm1.secondで割ればrm1.first余る
     * @param rm2 rm2.secondで割ればrm2.first余る
     * @return (r,m) mで割ればr余る
     */
    static Pairlonglong chineseRemainder(Pairlonglong rm1, Pairlonglong rm2){
        if(rm1==null||rm2==null){return null;}
        long[] exeuc=exeuc(rm1.second,rm2.second);
        //err.printf("gcd(%d,%d)=%d,%d*%d+%d*%d=%d\n",rm1.second,rm2.second,exeuc[0],rm1.second,exeuc[1],rm2.second,exeuc[2],exeuc[0]);
        Pairlonglong res=new Pairlonglong(0L,0L);
        res.second=rm1.second*rm2.second;
        res.first=(
                ((rm1.first*rm2.second)%res.second*exeuc[2])%res.second+
                        ((rm2.first*rm1.second)%res.second*exeuc[1])%res.second
        )%res.second;
        if(res.first<0){res.first+=res.second;}
        res.first/=exeuc[0];
        res.second/=exeuc[0];
        if((res.first%rm1.second!=rm1.first)||(res.first%rm2.second!=rm2.first)){
            return null;
        }
        return res;
    }
    static void _chineseRemainderTest(){
        IntStream.range(1,5).forEachOrdered(m1->{
            IntStream.range(0,m1).forEachOrdered(r1->{
                IntStream.range(1,5).forEachOrdered(m2->{
                    IntStream.range(0,m2).forEachOrdered(r2->{
                        Pairlonglong rm1=new Pairlonglong(r1,m1);
                        Pairlonglong rm2=new Pairlonglong(r2,m2);
                        Pairlonglong rm=chineseRemainder(rm1,rm2);
                        err.println(rm1+" + "+rm2+" = "+rm);
                    });
                });
            });
        });
    }
    static Pair<BigInteger,BigInteger> chineseRemainder(Pair<BigInteger,BigInteger> rm1, Pair<BigInteger,BigInteger> rm2){
        if(rm1==null||rm2==null){return null;}
        BigInteger[] exeuc=exeuc(rm1.second,rm2.second);
        //err.printf("gcd(%d,%d)=%d,%d*%d+%d*%d=%d\n",rm1.second,rm2.second,exeuc[0],rm1.second,exeuc[1],rm2.second,exeuc[2],exeuc[0]);
        Pair<BigInteger,BigInteger> res=new Pair<BigInteger,BigInteger>(BigInteger.ZERO,BigInteger.ZERO);
        res.second=rm1.second.multiply(rm2.second);
        res.first=(
                ((rm1.first.multiply(rm2.second)).mod(res.second).multiply(exeuc[2])).mod(res.second).add(
                        ((rm2.first.multiply(rm1.second)).mod(res.second).multiply(exeuc[1])).mod(res.second)
                )
        ).mod(res.second);
        if(res.first.signum()<0){res.first=res.first.add(res.second);}
        res.first=res.first.divide(exeuc[0]);
        res.second=res.second.divide(exeuc[0]);
        if((!res.first.mod(rm1.second).equals(rm1.first))||(!res.first.mod(rm2.second).equals(rm2.first))){
            return null;
        }
        return res;
    }

    static ArrayList<Integer> divList(int n) {
        ArrayList<Integer> div = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                div.add(i);
                if (i * i != n) {div.add(n / i);}
            }
        }
        return div;
    }
    static ArrayList<Long> divList(long n) {
        ArrayList<Long> div = new ArrayList<>();
        for (long i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                div.add(i);
                if (i * i != n) {div.add(n / i);}
            }
        }
        return div;
    }
    static HashSet<Integer> divSet(int n) {
        HashSet<Integer> div = new HashSet<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {div.add(i);div.add(n / i);}
        }
        return div;
    }
    static TreeSet<Long> divTSet(long n) {
        TreeSet<Long> div = new TreeSet<>();
        for (long i = 1; i * i <= n; i++) {
            if (n % i == 0) {div.add(i);div.add(n / i);}
        }
        return div;
    }
    static TreeSet<Integer> divTSet(int n) {
        TreeSet<Integer> div = new TreeSet<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {div.add(i);div.add(n / i);}
        }
        return div;
    }
    static HashSet<Long> divSet(long n) {
        HashSet<Long> div = new HashSet<>();
        for (long i = 1; i * i <= n; i++) {
            if (n % i == 0) {div.add(i);div.add(n / i);}
        }
        return div;
    }

    static HashMap<Long, Integer> pFacMap(long x) {
        HashMap<Long, Integer> mp = new HashMap<>();
        long t = x;
        for (long i = 2; i * i <= x && i <= t; i++) {
            if (t % i == 0) {
                int num = 0;
                while (t % i == 0) {
                    t /= i;
                    num++;
                }
                mp.put(i, num);
            }
        }
        if (t != 1) {
            mp.put(t, 1);
        }
        return mp;
    }
    static TreeMap<Long, Integer> pFacTMap(long x) {
        TreeMap<Long, Integer> mp = new TreeMap<>();
        long t = x;
        for (long i = 2; i * i <= x && i <= t; i++) {
            if (t % i == 0) {
                int num = 0;
                while (t % i == 0) {
                    t /= i;
                    num++;
                }
                mp.put(i, num);
            }
        }
        if (t != 1) {
            mp.put(t, 1);
        }
        return mp;
    }

    /**
     * 素数判定。実証されたミラーテストを用いる。
     * <a href="http://hp.vector.co.jp/authors/VA024411/js_calc/primality.html#miller">...</a>
     * <a href="https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95">...</a>
     * @param n 判定する整数
     * @return nが素数か
     */
    static boolean iP(long n) {
        if (n == 2) {return true;}
        if (n % 2 == 0 || n == 1) {return false;}
        long d = n - 1;
        while ((d & 1) == 0) {d /= 2;}
        int[] aa;
        if (n >= 341_550_071_728_321L) {
            aa = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        } else if (n >= 4_759_123_141L) {
            aa = new int[]{2, 3, 5, 7, 11, 13, 17};
        } else {
            aa = new int[]{2, 7, 61};
        }
        for (int i = 0; i < aa.length && aa[i] < n; i++) {
            int a = aa[i];
            long t = d;
            long y = repow(a, t, n);
            while (t != n - 1 && y != 1 && y != n - 1) {
                y = (y * y) % n;
                t = t << 1;
            }
            if (y != n - 1 && (t & 1) == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 二項係数とかクラス
     */
    static class NCK {
        int max;
        long mod;
        public long[] fac;
        public long[] finv;
        public long[] inv;
        public NCK() {this(510000);}
        public NCK(int max) {this(max, Main.mod);}
        public NCK(int max, long mod) {pre(max, mod);}
        /**
         * 初期化 使いまわすべくコンストラクタから分離
         * @param nmax 求めたいnCkのnの最大
         * @param nmod 法
         */
        public void pre(int nmax, long nmod) {
            this.max = nmax;
            this.mod = nmod;
            fac = new long[nmax];
            finv = new long[nmax];
            inv = new long[nmax];
            fac[0] = fac[1] = 1;
            finv[0] = finv[1] = 1;
            inv[1] = 1;
            for (int i = 2; i < nmax; i++) {
                fac[i] = fac[i - 1] * i % nmod;
                inv[i] = nmod - inv[(int) nmod % i] * (nmod / i) % nmod;
                finv[i] = finv[i - 1] * inv[i] % nmod;
            }
        }
        /**
         * nCkを返す。
         * @param n n個の中から
         * @param k k個選ぶ
         * @return nCk
         */
        public long nCk(int n, int k) {
            if (n < k) {return 0;}
            if (n < 0 || k < 0) {return 0;}
            return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
        }
        /**
         * nPkを返す。
         *
         * @param n n個の中から
         * @param k k個選ぶ
         * @return nPk
         */
        public long nPk(int n, int k) {
            if (n < k) {return 0;}
            if (n < 0 || k < 0) {return 0;}
            return (fac[n] * finv[n - k]) % mod;
        }
    }

    static long modinv(long a, long m) {
        long b = m, u = 1L, v = 0L;
        long tmp;
        while(b != 0L){
            long t = a / b;
            a -= t * b;
            tmp=a;a=b;b=tmp;
            u -= t * v;
            tmp=u;u=v;v=tmp;
        }
        u %= m;
        if (u < 0) u += m;
        return u;
    }

    static long modinv(long a) {
        long b = mod, u = 1L, v = 0L;
        long tmp;
        while(b != 0L){
            long t = a / b;
            a -= t * b;
            tmp=a;a=b;b=tmp;
            u -= t * v;
            tmp=u;u=v;v=tmp;
        }
        u %= mod;
        if (u < 0) u += mod;
        return u;
    }

    /**
     * t内でpと一致する最初の場所を検索。O(|t|+|p|)
     *
     * @param t テキスト
     * @param p パターン
     * @return t[i:i+|p|]=pとなる最小のi。無ければ-1。
     */
    static int kmp(String t, String p) {
        int[] f = new int[p.length() + 1];
        int i = 0, j = 1;
        f[1] = 0;
        while (j < p.length()) {
            if (i == 0 || p.charAt(i - 1) == p.charAt(j - 1)) {
                i++;
                j++;
                f[j] = i;
            } else {
                i = f[i];
            }
        }
        i = 1;
        j = 1;
        while (i <= p.length() && j <= t.length()) {
            if (i == 0 || p.charAt(i - 1) == t.charAt(j - 1)) {
                i++;
                j++;
            } else {
                i = f[i];
            }
        }
        return i == (p.length() + 1) ? j - i : -1;
    }

    /*
     * ランレングス圧縮
     */
    static List<Pair<Character,Integer>> rle(CharSequence s) {
        return _rleObject(s::charAt,s.length());
    }
    static List<Pairintint> _rleInt(IntUnaryOperator func,int size){
        if(size==0){return new ArrayList<>();}
        int ple=-1;
        List<Pairintint> res = new ArrayList<>();
        for (int i = 0; i+1 < size; i++) {
            if (func.applyAsInt(i) != func.applyAsInt(i+1)) {
                res.add(new Pairintint(func.applyAsInt(i), i-ple));
                ple=i;
            }
        }
        res.add(new Pairintint(func.applyAsInt(size-1), size-1-ple));
        return res;
    }
    static <T> List<Pair<T,Integer>> _rleObject(IntFunction<T> func,int size){
        if(size==0){return new ArrayList<>();}
        int ple=-1;
        List<Pair<T,Integer>> res = new ArrayList<>();
        for (int i = 0; i+1 < size; i++) {
            if (!func.apply(i).equals(func.apply(i+1))) {
                res.add(new Pair<>(func.apply(i), i-ple));
                ple=i;
            }
        }
        res.add(new Pair<>(func.apply(size-1), size-1-ple));
        return res;
    }

    static int lis(int[] a, boolean kyogi) {
        int res = -1;
        Integer[] dp = new Integer[a.length];
        Arrays.fill(dp, iMax);
        for (int i = 0; i < a.length; i++) {
            int ii=i;
            Predicate<Integer> isOk = kyogi?(am->am>=a[ii]):(am->am>a[ii]);
            Integer idx = bs(
                    x->dp[x],
                    -1, dp.length-1,
                    isOk,
                    (ng,ok)->(ng+ok)/2,
                    (ng,ok)->Math.abs(ok-ng)<=1
            );
            dp[idx] = a[i];
            res = Math.max(idx, res);
        }
        //print(dp,"",",","\n",err);
        return res + 1;
    }

    static class Zip1<T> {
        Map<T, Integer> zipMap;
        T[] unzipArray;
        Zip1(T[] a,int mapInitSsize,boolean needUnzip) {
            zipMap  = new HashMap<>();
            Arrays.sort(a);
            T last = null;
            int shift = 0;
            for (int i = 0; i < a.length; i++) {
                if (i == 0 || !last.equals(a[i])) {
                    zipMap.put(a[i], i - shift);
                    last = a[i];
                } else {
                    shift++;
                }
            }
            if(needUnzip){
                unzipArray = (T[]) (new Object[zipMap.size()]);
                for (Map.Entry<T, Integer> me : zipMap.entrySet()) {
                    unzipArray[me.getValue()] = me.getKey();
                }
            }
        }
        Integer zip(T t) {return zipMap.get(t);}
        T unzip(int i) {
            if(unzipArray==null){throw new UnsupportedOperationException("needUnzip is false.");}
            return unzipArray[i];
        }
        int size() {return zipMap.size();}
    }
    static class Zip1int {
        Map<Integer, Integer> zipMap;
        int[] unzipArray;
        Zip1int(int[] a,int mapInitSize,boolean needUnzip) {
            zipMap = new HashMap<>(mapInitSize);
            Arrays.sort(a);
            int last = -1;
            int shift = 0;
            for (int i = 0; i < a.length; i++) {
                if (i == 0 || last!=a[i]) {
                    zipMap.put(a[i], i - shift);
                    last = a[i];
                } else {
                    shift++;
                }
            }
            if(needUnzip){
                unzipArray = new int[zipMap.size()];
                for (Map.Entry<Integer, Integer> me : zipMap.entrySet()) {
                    unzipArray[me.getValue()] = me.getKey();
                }
            }
        }
        Integer zip(int t) {return zipMap.get(t);}
        int unzip(int i) {
            if(unzipArray==null){throw new UnsupportedOperationException("needUnzip is false.");}
            return unzipArray[i];
        }
        int size() {return zipMap.size();}
    }
    static class Zip1long {
        Map<Long, Integer> zipMap;
        long[] unzipArray;
        Zip1long(long[] a,int mapInitSize,boolean needUnzip) {
            zipMap = new HashMap<>(mapInitSize);
            Arrays.sort(a);
            long last = -1L;
            int shift = 0;
            for (int i = 0; i < a.length; i++) {
                if (i == 0 || last!=a[i]) {
                    zipMap.put(a[i], i - shift);
                    last = a[i];
                } else {
                    shift++;
                }
            }
            if(needUnzip){
                unzipArray = new long[zipMap.size()];
                for (Map.Entry<Long, Integer> me : zipMap.entrySet()) {
                    unzipArray[me.getValue()] = me.getKey();
                }
            }
        }
        Integer zip(long t) {return zipMap.get(t);}
        long unzip(int i) {
            if(unzipArray==null){throw new UnsupportedOperationException("needUnzip is false.");}
            return unzipArray[i];
        }
        int size() {return zipMap.size();}
    }

    static class UnFd {
        protected int n;
        protected int[] parent;
        protected int[] size;
        protected int forest;
        UnFd(int n) {
            this.n=n;
            parent = new int[n];
            size = new int[n];
            forest = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        boolean isRoot(int i) {return parent[i] == i;}
        int rootOf(int i){
            if(isRoot(i)){return i;}
            return parent[i] = rootOf(parent[i]);
        }
        public boolean same(int i, int j) {return rootOf(i) == rootOf(j);}
        public void merge(int i, int j) {
            i=rootOf(i);j=rootOf(j);
            if(i==j){return;}
            //if(i<j){
            if(size[i]>size[j]){
                _merge(i,j);
            }else{
                _merge(j,i);
            }
        }
        protected void _merge(int trunk,int branch){
            size[trunk]+=size[branch];
            parent[branch]=trunk;
            forest--;
        }
        public int sizeOf(int i) {return size[rootOf(i)];}
        public int[] parentSafe() {
            return Arrays.copyOf(parent,parent.length);
        }
        public int parentOf(int i){return parent[i];}
        public int forest() {return forest;}
        public Map<Integer,List<Integer>> calcGroups(){
            Map<Integer,List<Integer>> res=new HashMap<>();
            for(int i=0;i<parent.length;i++){
                if(!res.containsKey(rootOf(i))){res.put(rootOf(i),new ArrayList<>());}
                res.get(rootOf(i)).add(i);
            }
            return res;
        }
        public String toString() {return Arrays.toString(parent);}
    }

    static class WUnFd<T> {
        int[] parent;
        T[] relItoP;
        T zero;
        BinaryOperator<T> add;
        UnaryOperator<T> minus;
        int[] size;
        int forest;
        WUnFd(int n,T zero,BinaryOperator<T> add,UnaryOperator<T> minus) {
            parent = new int[n];
            relItoP =(T[]) Array.newInstance(zero.getClass(), n);
            this.zero=zero;
            this.add=add;
            this.minus=minus;
            size = new int[n];
            forest = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
                relItoP[i] = zero;
            }
        }
        boolean isRoot(int i) {return parent[i] == i;}
        int rootOf(int i){
            if(isRoot(i)){return i;}
            int root=rootOf(parent[i]);
            relItoP[i]=add.apply(relItoP[parent[i]], relItoP[i]);
            parent[i]=root;
            return parent[i];
        }
        public boolean same(int i, int j) {
            return rootOf(i)==rootOf(j);
        }
        public T relFtoT(int f, int t) {
            return same(f,t)?add.apply(relItoP[f],minus.apply(relItoP[t])):null;
        }
        public boolean merge(int f, int t,T relFtoT) {
            //err.printf("[MERGE A%d + %s = A%d]\n",f,relFtoT,t);
            int rootf=rootOf(f);
            int roott=rootOf(t);
            if (rootf==roott) {
                //err.printf("""
                //    ----------
                //        %d
                //    ^       ^
                //    %s       %s
                //    |       |
                //    %d -(%s)->%d
                //    ----------
                //    """,
                //    rootf,
                //    relItoP[f],relItoP[t],
                //    f,relFtoT,t
                //);
                return add.apply(relItoP[f],minus.apply(relItoP[t])).equals(relFtoT);
            }
            T relRFtoRT=add.apply(add.apply(relFtoT, relItoP[t]),minus.apply(relItoP[f]));

            //err.printf("""
            //        ----------
            //        %d -(%s)->%d
            //        ^       ^
            //        %s       %s
            //        |       |
            //        %d -(%s)->%d
            //        ----------
            //        """,
            //        rootf,relRFtoRT,roott,
            //        relItoP[f],relItoP[t],
            //        f,relFtoT,t);
            //if(size[rootf]>size[roott]){
            //    int tmp=rootf;rootf=roott;roott=tmp;
            //    relRFtoRT=minus.apply(relRFtoRT);
            //}
            size[roott] += size[rootf];
            parent[rootf] = roott;
            relItoP[rootf] = relRFtoRT;
            forest--;
            return true;
        }
        public int sizeOf(int i) {
            return size[rootOf(i)];
        }
        public int[] parents() {
            return parent;
        }
        public T[] rels() {
            return relItoP;
        }
        public int forest() {
            return forest;
        }
        public Map<Integer,List<Integer>> calcGroups(){
            Map<Integer,List<Integer>> res=new HashMap<>();
            for(int i=0;i<parent.length;i++){
                if(!res.containsKey(rootOf(i))){
                    res.put(rootOf(i),new ArrayList<>());
                }
                res.get(rootOf(i)).add(i);
            }
            return res;
        }
        public Map<Integer,List<Pair<Integer,T>>> calcGroupsWithRelation(){
            Map<Integer,List<Pair<Integer,T>>> res=new HashMap<>();
            for(int i=0;i<parent.length;i++){
                int root=rootOf(i);
                if(!res.containsKey(root)){
                    res.put(root,new ArrayList<>());
                }
                res.get(root).add(new Pair<>(i,relItoP[i]));
            }
            return res;
        }
        public String toString() {
            return Arrays.toString(parent)+","+Arrays.toString(relItoP);
        }
        public void debug(PrintWriter pw){
            if(onlineJudge){return;}
            for(int i=0;i<parent.length;i++){
                pw.printf("A%d + %s = A%d\n",i,relItoP[i],parent[i]);
            }pw.println();
        }
    }

    static class SegTreeInt {
        final int n;//数列の長さ
        final int m;//木の頂点数
        final IntBinaryOperator merge;
        final int identity;
        final int[] l;
        final int[] r;//頂点iは区間[l[i],r[i])を表す
        final int[] a;
        private final int[] res;
        private final Deque<Integer> stack=new ArrayDeque<>();

        private SegTreeInt(IntBinaryOperator merge,int n,int identity) {
            this.n=n;
            this.m=(Integer.highestOneBit((n<<2)-1))-1;
            this.merge=merge;
            this.identity=identity;
            a=new int[m];
            l=new int[m];
            r=new int[m];
            for(int i=0;i<=m/2;i++) {
                l[m/2+i]=i;
                r[m/2+i]=i+1;
            }
            for (int i=m/2-1;i>=0;i--) {
                l[i]=l[lchild(i)];
                r[i]=r[rchild(i)];
            }
            res=new int[m];
        }
        SegTreeInt(int n,IntBinaryOperator merge,int identity) {
            this(merge,n,identity);
            Arrays.fill(a,identity);
        }
        SegTreeInt(int n,IntBinaryOperator merge,int identity,int[] ary){
            this(merge,n,identity);
            if (n>=0)System.arraycopy(ary,0,a,m/2,n);
            Arrays.fill(a,m/2+n,m,identity);
            for(int i=m/2-1;i>=0;i--){
                a[i]=merge.applyAsInt(a[lchild(i)],a[rchild(i)]);
            }
        }
        public int get(int from,int to) {
            if(from==to){return identity;}
            if(from<0||n<to||from>to){throw new IllegalArgumentException(from+","+to);}
            stack.addLast(0);
            while(!stack.isEmpty()){
                int node=stack.pollLast();
                if(node>=0){
                    if(from<=l[node]&&r[node]<=to){
                        res[node]=a[node];
                    }else{
                        int center=r[lchild(node)];
                        stack.addLast(~node);
                        if (to <= center) {
                            stack.addLast(lchild(node));
                        } else if (center <= from) {
                            stack.addLast(rchild(node));
                        } else {
                            stack.addLast(lchild(node));
                            stack.addLast(rchild(node));
                        }
                    }
                }else{
                    int center=r[lchild(~node)];
                    if (to <= center) {
                        res[~node]=res[lchild(~node)];
                    } else if (center <= from) {
                        res[~node]=res[rchild(~node)];
                    } else {
                        res[~node]= merge.applyAsInt(res[lchild(~node)],res[rchild(~node)]);
                    }
                }
            }
            return res[0];
        }
        public void set(int ob,int i){
            if(i<0||n<=i){throw new IndexOutOfBoundsException(i + "isOutFromLength " + n);}
            int j=m/2+i;
            a[j]=ob;
            while(j!=0){
                j=parent(j);
                a[j]= merge.applyAsInt(a[lchild(j)],a[rchild(j)]);
            }
        }
        public void update(IntUnaryOperator updater,int i){
            if(i<0||n<=i){throw new IndexOutOfBoundsException(i + "isOutFromLength " + n);}
            int j=m/2+i;
            int newaj=updater.applyAsInt(a[j]);
            if(a[j]==newaj){return;}
            a[j]=newaj;
            while(j!=0){
                j=parent(j);
                a[j]=merge.applyAsInt(a[lchild(j)],a[rchild(j)]);
            }
        }
        static private int parent(int node){return (node-1)/2;}
        static private int lchild(int node){return 2*node+1;}
        static private int rchild(int node){return 2*node+2;}
        public String toString(){return Arrays.toString(a);}
    }
    static class SegTreeLong {
        final int n;//数列の長さ
        final int m;//木の頂点数
        final LongBinaryOperator merge;
        final long identity;
        final int[] l;
        final int[] r;//頂点iは区間[l[i],r[i])を表す
        final long[] a;
        private final long[] res;
        private final Deque<Integer> stack=new ArrayDeque<>();

        private SegTreeLong(LongBinaryOperator merge,int n,long identity) {
            this.n=n;
            this.m=(Integer.highestOneBit((n<<2)-1))-1;
            this.merge=merge;
            this.identity=identity;
            a=new long[m];
            l=new int[m];
            r=new int[m];
            for(int i=0;i<=m/2;i++) {
                l[m/2+i]=i;
                r[m/2+i]=i+1;
            }
            for (int i=m/2-1;i>=0;i--) {
                l[i]=l[lchild(i)];
                r[i]=r[rchild(i)];
            }
            res=new long[m];
        }
        SegTreeLong(int n,LongBinaryOperator merge,long identity) {
            this(merge,n,identity);
            Arrays.fill(a,identity);
        }
        SegTreeLong(int n,LongBinaryOperator merge,long identity,int[] ary){
            this(merge,n,identity);
            if (n>=0)System.arraycopy(ary,0,a,m/2,n);
            Arrays.fill(a,m/2+n,m,identity);
            for(int i=m/2-1;i>=0;i--){
                a[i]=merge.applyAsLong(a[lchild(i)],a[rchild(i)]);
            }
        }
        public long get(int from,int to) {
            if(from==to){return identity;}
            if(from<0||n<to||from>to){throw new IllegalArgumentException(from+","+to);}
            stack.addLast(0);
            while(!stack.isEmpty()){
                int node=stack.pollLast();
                if(node>=0){
                    if(from<=l[node]&&r[node]<=to){
                        res[node]=a[node];
                    }else{
                        int center=r[lchild(node)];
                        stack.addLast(~node);
                        if (to <= center) {
                            stack.addLast(lchild(node));
                        } else if (center <= from) {
                            stack.addLast(rchild(node));
                        } else {
                            stack.addLast(lchild(node));
                            stack.addLast(rchild(node));
                        }
                    }
                }else{
                    int center=r[lchild(~node)];
                    if (to <= center) {
                        res[~node]=res[lchild(~node)];
                    } else if (center <= from) {
                        res[~node]=res[rchild(~node)];
                    } else {
                        res[~node]= merge.applyAsLong(res[lchild(~node)],res[rchild(~node)]);
                    }
                }
            }
            return res[0];
        }
        public void set(long ob,int i){
            if(i<0||n<=i){throw new IndexOutOfBoundsException(i + "isOutFromLength " + n);}
            int j=m/2+i;
            a[j]=ob;
            while(j!=0){
                j=parent(j);
                a[j]= merge.applyAsLong(a[lchild(j)],a[rchild(j)]);
            }
        }
        public void update(LongUnaryOperator updater,int i){
            if(i<0||n<=i){throw new IndexOutOfBoundsException(i + "isOutFromLength " + n);}
            int j=m/2+i;
            a[j]=updater.applyAsLong(a[j]);
            while(j!=0){
                j=parent(j);
                a[j]=merge.applyAsLong(a[lchild(j)],a[rchild(j)]);
            }
        }
        static private int parent(int node){return (node-1)/2;}
        static private int lchild(int node){return 2*node+1;}
        static private int rchild(int node){return 2*node+2;}
        public String toString(){return Arrays.toString(a);}
    }
    static class SegTree<E> {
        final int n;//数列の長さ
        final int m;//木の頂点数
        final BinaryOperator<E> merge;
        final E identity;
        final int[] l;
        final int[] r;//頂点iは区間[l[i],r[i])を表す
        final E[] a;
        private final E[] res;
        private final Deque<Integer> stack=new ArrayDeque<>();

        private SegTree(BinaryOperator<E> merge,int n,E identity) {
            this.n=n;
            this.m=(Integer.highestOneBit((n<<2)-1))-1;
            this.merge=merge;
            this.identity=identity;
            @SuppressWarnings("unchecked")
            E[] b=(E[])(new Object[m]);
            a=b;
            l=new int[m];
            r=new int[m];
            for(int i=0;i<=m/2;i++) {
                l[m/2+i]=i;
                r[m/2+i]=i+1;
            }
            for (int i=m/2-1;i>=0;i--) {
                l[i]=l[lchild(i)];
                r[i]=r[rchild(i)];
            }
            @SuppressWarnings("unchecked")
            E[] sft=(E[])new Object[m];
            res=sft;
        }
        SegTree(int n,BinaryOperator<E> merge,E identity) {
            this(merge,n,identity);
            Arrays.fill(a,identity);
        }
        SegTree(int n,BinaryOperator<E> merge,E identity,E[] ary){
            this(merge,n,identity);
            if (n>=0)System.arraycopy(ary,0,a,m/2,n);
            Arrays.fill(a,m/2+n,m,identity);
            for(int i=m/2-1;i>=0;i--){
                a[i]=merge.apply(a[lchild(i)],a[rchild(i)]);
            }
        }
        public E get(int from,int to) {
            if(from==to){return identity;}
            if(from<0||n<to||from>to){throw new IllegalArgumentException(from+","+to);}
            stack.addLast(0);
            while(!stack.isEmpty()){
                int node=stack.pollLast();
                if(node>=0){
                    if(from<=l[node]&&r[node]<=to){
                        res[node]=a[node];
                    }else{
                        int center=r[lchild(node)];
                        stack.addLast(~node);
                        if (to <= center) {
                            stack.addLast(lchild(node));
                        } else if (center <= from) {
                            stack.addLast(rchild(node));
                        } else {
                            stack.addLast(lchild(node));
                            stack.addLast(rchild(node));
                        }
                    }
                }else{
                    int center=r[lchild(~node)];
                    if (to <= center) {
                        res[~node]=res[lchild(~node)];
                    } else if (center <= from) {
                        res[~node]=res[rchild(~node)];
                    } else {
                        res[~node]= merge.apply(res[lchild(~node)],res[rchild(~node)]);
                    }
                }
            }
            return res[0];
        }
        public void set(E ob,int i){
            if(i<0||n<=i){throw new IndexOutOfBoundsException(i + "isOutFromLength " + n);}
            int j=m/2+i;
            a[j]=ob;
            while(j!=0){
                j=parent(j);
                a[j]= merge.apply(a[lchild(j)],a[rchild(j)]);
            }
        }
        public void update(UnaryOperator<E> updater,int i){
            if(i<0||n<=i){throw new IndexOutOfBoundsException(i + "isOutFromLength " + n);}
            int j=m/2+i;
            a[j]=updater.apply(a[j]);
            while(j!=0){
                j=parent(j);
                a[j]= merge.apply(a[lchild(j)],a[rchild(j)]);
            }
        }
        static private int parent(int node){return (node-1)/2;}
        static private int lchild(int node){return 2*node+1;}
        static private int rchild(int node){return 2*node+2;}
        public String toString(){return Arrays.toString(a);}
    }

    static class LazySegTree<E,L> {
        final int n;//数列の長さ
        final int m;//木の頂点数
        final BinaryOperator<E> mergeE;//要素の合成
        final BinaryOperator<L> mergeL;//遅延情報の合成
        final LApply2E<E,L> lApply2E;//遅延情報の適用
        final E identity;
        final int[] l;
        final int[] r;//頂点iは区間[l[i],r[i])を表す
        final E[] a;
        final L[] c;
        private final E[] res;//非再帰化した際に必要になったやつ
        private final Deque<Integer> stack=new ArrayDeque<>();

        private LazySegTree(BinaryOperator<E> mergeE,BinaryOperator<L> mergeL,LApply2E<E,L> lApply2E,int n,E identity){
            this.n = n;
            this.m = (Integer.highestOneBit((n << 2) - 1)) - 1;
            this.mergeE = mergeE;
            this.mergeL = mergeL;
            this.lApply2E = lApply2E;
            this.identity = identity;
            @SuppressWarnings("unchecked")
            E[] b = (E[]) (new Object[m]);
            a = b;
            @SuppressWarnings("unchecked")
            L[] d = (L[]) (new Object[m]);
            c = d;
            l = new int[m];
            r = new int[m];
            for (int i=0;i<=m/2;i++) {
                l[m/2+i]=i;
                r[m/2+i]=i+1;
            }
            for (int i=m/2-1;i>=0;i--) {
                l[i]=l[lchild(i)];
                r[i]=r[rchild(i)];
            }
            @SuppressWarnings("unchecked")
            E[] sft = (E[]) (new Object[m]);
            res=sft;
        }

        public LazySegTree(int n,BinaryOperator<E> mergeE,BinaryOperator<L> mergeL,LApply2E<E,L> lApply2E,E identity) {
            this(mergeE, mergeL,lApply2E, n, identity);
            Arrays.fill(a, identity);
        }

        public LazySegTree(int n,BinaryOperator<E> mergeE,BinaryOperator<L> mergeL,LApply2E<E,L> lApply2E,E identity,E[] ary) {
            this(mergeE, mergeL,lApply2E, n, identity);
            if (n >= 0){ System.arraycopy(ary,0,a,m/2, n);}

            Arrays.fill(a,m/2+n,m,identity);
            for (int i=m/2-1;i>=0;i--) {
                a[i] = mergeE.apply(a[lchild(i)], a[rchild(i)]);
            }
        }

        public E get(int from,int to){
            if(from==to){return identity;}
            if(from<0||n<to||from>to){throw new IllegalArgumentException(from+","+to);}
            stack.addLast(0);
            while(!stack.isEmpty()){
                int node=stack.pollLast();
                if(node>=0){
                    eval(node);
                    if(from<=l[node]&&r[node]<=to){
                        res[node]=a[node];
                    }else{
                        int center=r[lchild(node)];
                        stack.addLast(~node);
                        if(to<=center){
                            stack.addLast(lchild(node));
                        }else if(center<=from){
                            stack.addLast(rchild(node));
                        }else{
                            stack.addLast(lchild(node));
                            stack.addLast(rchild(node));
                        }
                    }
                }else{
                    int center=r[lchild(~node)];
                    if(to<=center){
                        res[~node]=res[lchild(~node)];
                    }else if(center<=from){
                        res[~node]=res[rchild(~node)];
                    }else{
                        res[~node]=mergeE.apply(res[lchild(~node)],res[rchild(~node)]);
                    }
                }
            }
            return res[0];
        }

        private void eval(int node){
            //err.println("E"+node+":"+c[node]);
            if(c[node]==null){return;}
            a[node]= lApply2E.apply(a[node],c[node],r[node]-l[node]);
            if(r[node]-l[node]>1){
                c[lchild(node)]=c[lchild(node)]==null?c[node]: mergeL.apply(c[lchild(node)],c[node]);
                c[rchild(node)]=c[rchild(node)]==null?c[node]: mergeL.apply(c[rchild(node)],c[node]);
            }
            c[node]=null;
        }

        public void set(L u,int from,int to){
            if(from==to){return;}
            if(from<0||n<to||from>to){throw new IllegalArgumentException(from+","+to);}
            stack.addLast(0);
            while(!stack.isEmpty()){
                int node=stack.pollLast();
                if(node>=0){
                    if(from<=l[node]&&r[node]<=to){
                        c[node]=c[node]==null?u: mergeL.apply(c[node],u);
                        eval(node);
                    }else{
                        eval(node);
                        int center=r[lchild(node)];
                        stack.addLast(~node);
                        if(to<=center){
                            eval(rchild(node));
                            stack.addLast(lchild(node));
                        }else if(center<=from){
                            eval(lchild(node));
                            stack.addLast(rchild(node));
                        }else{
                            stack.addLast(lchild(node));
                            stack.addLast(rchild(node));
                        }
                    }
                }else{
                    a[~node]=mergeE.apply(a[lchild(~node)],a[rchild(~node)]);
                }
            }
        }

        static private int parent(int node){return (node-1)/2;}
        static private int lchild(int node){return 2*node+1;}
        static private int rchild(int node){return 2*node+2;}
        public String toString() {return Arrays.toString(a);}
        public void debug(int width){
            if(onlineJudge){return;}
            String space=IntStream.range(0,width).mapToObj((i)->" ").collect(Collectors.joining());
            err.print(debugPrint(0,width)+" ");
            int ple=n;
            for(int i=1;i<m;i++){
                if(ple!=r[i]-l[i]){
                    err.println();
                    ple=r[i]-l[i];
                }
                err.print(debugPrint(i,width)+" ");
                for(int j=1;j<ple;j++){
                    err.print(space+" ");
                }
            }
            err.println();
            err.println();
        }
        private String debugPrint(int node,int width){
            String res=String.format("%02d:%s/%s",node,a[node],c[node]);
            String space= IntStream.range(0,width-res.length()).mapToObj((i)->" ").collect(Collectors.joining());
            return res+space;
        }
        private interface LApply2E<E,L>{ E apply(E e, L l, int w);}
    }

    static class DualSegTree<U> {
        final int n;//数列の長さ
        final int m;//木の頂点数
        final BinaryOperator<U> mergeL;//遅延情報の合成
        final int[] l;
        final int[] r;//頂点iは区間[l[i],r[i])を表す
        final U[] c;
        private final Deque<Integer> stack=new ArrayDeque<>();

        private DualSegTree(BinaryOperator<U> mergeL, int n) {
            this.n=n;
            this.m=(Integer.highestOneBit((n<<2)-1))-1;
            this.mergeL=mergeL;
            @SuppressWarnings("unchecked")
            U[] d=(U[])(new Object[m]);
            c=d;
            l=new int[m];r=new int[m];
            for(int i=0;i<=m/2;i++){
                l[m/2+i]=i;
                r[m/2+i]=i+1;
            }
            for(int i=m/2-1;i>=0;i--){
                l[i]=l[lchild(i)];
                r[i]=r[rchild(i)];
            }
        }
        public DualSegTree(int n,BinaryOperator<U> op2){this(op2,n);}
        public DualSegTree(int n,BinaryOperator<U> op2,U[] ary) {
            this(op2,n);
            if(n>=0){System.arraycopy(ary,0,c,m/2,n);}
        }
        public U get(int i){
            if (i<0||n<i+1){throw new IllegalArgumentException(i+"");}
            int node=0;
            while(true){
                eval(node);
                if(l[node]==i&&r[node]==i+1){break;}
                int center=r[lchild(node)];
                if (i+1<=center) {
                    node=lchild(node);
                } else {
                    node=rchild(node);
                }
            }
            return c[node];
        }
        private void eval(int node){
            //err.println("E"+node+":"+c[node]);
            if(c[node]==null){return;}
            if(r[node]-l[node]>1){
                c[lchild(node)]=c[lchild(node)]==null?c[node]:mergeL.apply(c[lchild(node)],c[node]);
                c[rchild(node)]=c[rchild(node)]==null?c[node]:mergeL.apply(c[rchild(node)],c[node]);
                c[node]=null;
            }
        }
        public void set(U u,int from,int to){
            if (from == to) {return;}
            if (from<0||n<to||from>to){throw new IllegalArgumentException(from+","+to);}
            stack.addLast(0);
            while(!stack.isEmpty()){
                int node=stack.pollLast();
                if(from<=l[node]&&r[node]<=to){
                    c[node]=c[node]==null?u:mergeL.apply(c[node],u);
                }else{
                    eval(node);
                    int center=r[lchild(node)];
                    if(to <= center){
                        stack.addLast(lchild(node));
                    }else if(center<=from){
                        stack.addLast(rchild(node));
                    }else{
                        stack.addLast(lchild(node));
                        stack.addLast(rchild(node));
                    }
                }
            }
        }
        static private int parent(int node){return (node-1)/2;}
        static private int lchild(int node){return 2*node+1;}
        static private int rchild(int node){return 2*node+2;}
        public String toString(){return Arrays.toString(c);}
        public void debug(int width){
            if(onlineJudge){return;}
            String space= IntStream.range(0,width).mapToObj((i)->" ").collect(Collectors.joining());
            err.print(debugPrint(0,width)+" ");
            int ple=n;
            for(int i=1;i<m;i++){
                if(ple!=r[i]-l[i]){
                    err.println();
                    ple=r[i]-l[i];
                }
                err.print(debugPrint(i,width)+" ");
                for(int j=1;j<ple;j++){
                    err.print(space+" ");
                }
            }
            err.println();
            err.println();
        }
        private String debugPrint(int node,int width){
            String res=String.format("%02d:%s",node,c[node]);
            String space= IntStream.range(0,width-res.length()).mapToObj((i)->" ").collect(Collectors.joining());
            return res+space;
        }
    }

    static class SparseTable<T>{
        int[] log;//
        BinaryOperator<T> op;
        T ident;
        T[][] a;
        //a[i][j]:= jを左端とする長さ2^iの区間についての答え
        //          区間[j,j+2^i)
        int n;
        public SparseTable(T[] array,BinaryOperator<T> op,T ident){
            this.op=op;
            n=array.length;
            this.ident=ident;
            int p=0;
            {
                int len=1;
                while(len<=n){p++;len<<=1;}
            }
            @SuppressWarnings("unchecked")
            T[][] b=(T[][])new Object[p][];
            a=b;
            log=new int[n+1];
            int len=1;
            for(int i=0;i<p;i++){
                @SuppressWarnings("unchecked")
                T[] bj=(T[])new Object[n-len+1];
                a[i]=bj;
                for(int j=0;j<a[i].length;j++){
                    a[i][j]=i==0?
                            array[j]:
                            op.apply(a[i-1][j],a[i-1][j+len/2]);
                }
                len<<=1;
            }
            for(int i=2;i<=n;i++){log[i]=log[i>>1]+1;}
        }
        public T get(int left,int right){
            int len=right-left;
            if(len<=0){return ident;}
            return op.apply(
                    a[log[len]][left],
                    a[log[len]][right-(1<<log[len])]
            );
        }
    }
    static class IntSparseTable{
        int[] log;//
        IntBinaryOperator op;
        int ident;
        int[][] a;
        //a[i][j]:= jを左端とする長さ2^iの区間についての答え
        //          区間[j,j+2^i)
        int n;
        public IntSparseTable(int[] array,IntBinaryOperator op,int ident){
            this.op=op;
            n=array.length;
            this.ident=ident;
            int p=0;
            {
                int len=1;
                while(len<=n){p++;len<<=1;}
            }
            a=new int[p][];
            log=new int[n+1];
            int len=1;
            for(int i=0;i<p;i++){
                a[i]=new int[n-len+1];
                for(int j=0;j<a[i].length;j++){
                    a[i][j]=i==0?
                            array[j]:
                            op.applyAsInt(a[i-1][j],a[i-1][j+len/2]);
                }
                len<<=1;
            }
            for(int i=2;i<=n;i++){log[i]=log[i>>1]+1;}
        }

        /**
         * 区間に演算した結果
         * @param left 含む
         * @param right 含まない
         * @return 区間に演算した結果
         */
        public int get(int left,int right){
            int len=right-left;
            if(len<=0){return ident;}
            return op.applyAsInt(
                    a[log[len]][left],
                    a[log[len]][right-(1<<log[len])]
            );
        }
    }

    static class BITreelong{
        int size;
        List<Long> list;
        public BITreelong(int initSize){list=new ArrayList<>(initSize);}
        //[0,r)の和
        public long get0_a(int r){
            long res=0L;
            while(r>0){
                res+=list.get(r-1);
                r=r&(r-1);
            }
            return res;
        }
        public long getl_r(int l,int r){return get0_a(r)-get0_a(l);}
        public void append(long v){
            // [ (size)&&(size+1), (size+1) )を追加
            // => [ (size)&(size+1), (size) ) + v
            list.add(get0_a(size)-get0_a(size&(size+1))+v);
            size++;
        }
        public void addAt(long v,int idx){
            idx++;
            while(idx<=size){
                list.set(idx-1,list.get(idx-1)+v);
                idx+=idx&-idx;
            }
        }
        public String toString(){return list.toString();}
    }

    static boolean next_permutation(int[] per) {
        if(per.length<2){return false;}
        int i;
        for(i=per.length-1;i>0;i--){if(per[i-1]<per[i]){break;}}
        if(0<i){
            i--;
            int j;
            for(j=per.length-1;j>i;j--){if(per[j]>per[i]){break;}}
            int tmp;
            //swap(i,j)
            tmp=per[i];per[i]=per[j];per[j]=tmp;
            for (int k=i+1;k<(i+1+per.length)/2;k++) {
                //swap(k,per.length-k+i)
                tmp=per[k];per[k]=per[per.length-k+i];per[per.length-k+i]=tmp;
            }
            return true;
        }
        int tmp;
        for (int k=0;k<per.length;k++) {
            //swap(k,per.length-k-1)
            tmp=per[k];per[k]=per[per.length-k-1];per[per.length-k-1]=tmp;
        }
        return false;
    }

    static <T> Iterator<T> countMap2Iterator(Map<T,? extends Number> map){
        return new Iterator<T>() {
            private Iterator<? extends Map.Entry<T, ? extends Number>> mapIt;
            private T e=null;
            private long remain=0L;

            Iterator<T> construct(Map<T,? extends Number> map){
                mapIt=map.entrySet().iterator();
                update();
                return this;
            }
            private void update(){
                while(remain<=0L&&mapIt.hasNext()){
                    Map.Entry<T, ? extends Number> kv=mapIt.next();
                    e=kv.getKey();
                    remain=kv.getValue().longValue();
                }
            }
            public boolean hasNext() {return remain>0L;}
            public T next() {
                T res=e;
                remain--;update();
                return res;
            }
        }.construct(map);
    }
    static class ExtMapLong<T> {
        private final Map<T, Long> map;
        private final boolean delete_zero;
        public ExtMapLong(Map<T, Long> map, boolean deleteZero) {
            this.map = map;
            this.delete_zero = deleteZero;
        }
        public ExtMapLong(Map<T, Long> map) {
            this(map, false);
        }
        public ExtMapLong() {
            this(new HashMap<T, Long>(), false);
        }
        public long get(T key) {
            return map.getOrDefault(key, 0L);
        }
        public long add(T key, long addValue) {
            long afterValue = get(key) + addValue;

            afterValue %=mod;

            if (delete_zero && afterValue == 0) {
                map.remove(key);
            } else {
                map.put(key, afterValue);
            }
            return afterValue;
        }
        public Map<T, Long> getMapShare() {
            return map;
        }
        public Map<T, Long> getMapSafety() {
            return new HashMap<>(map);
        }
        public String toString(){
            return map.toString();
        }
    }
    static class ExtMapInt<T> {
        private final Map<T, Integer> map;
        private final boolean delete_zero;
        public ExtMapInt(Map<T, Integer> map, boolean deleteZero) {
            this.map = map;
            this.delete_zero = deleteZero;
        }
        public ExtMapInt(Map<T, Integer> map) {
            this(map, false);
        }
        public ExtMapInt() {
            this(new HashMap<T, Integer>(), false);
        }
        public int get(T key) {
            return map.getOrDefault(key, 0);
        }
        public int add(T key, int addValue) {
            int afterValue = get(key) + addValue;
            if (delete_zero && afterValue == 0) {
                map.remove(key);
            } else {
                map.put(key, afterValue);
            }
            return afterValue;
        }
        public Map<T, Integer> getMapShare() {
            return map;
        }
        public Map<T, Integer> getMapSafety() {
            return new HashMap<>(map);
        }
        public String toString(){
            return map.toString();
        }
    }

    /**
     * 連続する要素を[key,val)にまとめて何やかやを効率的にするやつ
     * NavigableSet<Integer>の実装が不完全
     * ceil_ex(0)で0以上の含まない最小の整数(mex)が取れる
     */
    static class MEXSet implements NavigableSet<Integer>{
        private int size;
        private final TreeMap<Integer,Integer> treeMap;
        MEXSet(){
            treeMap=new TreeMap<>();
            size=0;
        }
        MEXSet(MEXSet mset){
            treeMap=new TreeMap<>(mset.treeMap);
            size=mset.size;
        }
        public int ceil_ex(int k){
            Map.Entry<Integer, Integer> a=treeMap.floorEntry(k);
            if(a==null){return k;}
            if(a.getValue()<=k){return k;}
            return a.getValue();
        }
        public int higher_ex(int k){
            return ceil_ex(k+1);
        }
        public int floor_ex(int k){
            Map.Entry<Integer, Integer> a=treeMap.floorEntry(k);
            if(a==null||a.getValue()<=k){return k;}
            return a.getKey()-1;
        }
        public int lower_ex(int k){
            return floor_ex(k-1);
        }
        @Override
        public Integer lower(Integer e){
            return floor(e-1);
        }
        @Override
        public Integer floor(Integer e){
            Map.Entry<Integer,Integer> left_lr=treeMap.floorEntry(e);
            if(left_lr==null){return null;}
            return min(left_lr.getValue()-1,e);
        }
        @Override
        public Integer ceiling(Integer e){
            Map.Entry<Integer,Integer> left_lr=treeMap.floorEntry(e);
            if(left_lr!=null && e<left_lr.getValue()){return e;}
            return treeMap.ceilingKey(e);
        }
        @Override
        public Integer higher(Integer e) {
            return ceiling(e+1);
        }
        @Override
        public Integer pollFirst(){
            Map.Entry<Integer,Integer> me=treeMap.firstEntry();
            if(me==null){return null;}
            treeMap.remove(me.getKey());
            treeMap.put(me.getKey()+1,me.getValue());
            size--;
            return me.getKey();
        }
        @Override
        public Integer pollLast(){
            Map.Entry<Integer,Integer> me=treeMap.pollFirstEntry();
            if(me==null){return null;}
            treeMap.remove(me.getKey());
            treeMap.put(me.getKey()+1,me.getValue());
            size--;
            return me.getKey();
        }
        @Override
        public int size() {
            return size;
        }
        @Override
        public boolean isEmpty() {
            return treeMap.isEmpty();
        }
        @Override
        public boolean contains(Object o){
            int e=(Integer)o;
            Map.Entry<Integer, Integer> lr=treeMap.floorEntry(e);
            return lr!=null && e<lr.getValue();
        }
        @Override
        public Iterator<Integer> iterator(){
            return new Iterator<Integer>() {
                List<Pairintint> lrList;
                Iterator<Pairintint> it;
                int right;
                int cursor;
                @Override
                public boolean hasNext() {
                    return cursor<right;
                }
                @Override
                public Integer next() {
                    int res=cursor;
                    step();
                    return res;
                }
                private void step(){
                    cursor++;
                    if(right<=cursor){
                        if(it.hasNext()){
                            Pairintint pii=it.next();
                            cursor=pii.first;
                            right=pii.second;
                        }
                    }
                }
                private Iterator<Integer> constructor(TreeMap<Integer,Integer> map){
                    lrList=new ArrayList<>(size());
                    int idx=size()-1;
                    map.forEach((l,r)->lrList.add(new Pairintint(l,r)));
                    right=0;cursor=0;
                    step();
                    return this;
                }
            }.constructor(treeMap);
        }
        @Override
        public Object[] toArray(){
            List<Object> list = new ArrayList<>(this);
            return list.toArray();
        }
        @Override
        public <T> T[] toArray(T[] a){
            if (a.length < size()) {
                return (T[]) Arrays.copyOf(toArray(), size(), a.getClass());
            }
            System.arraycopy(toArray(), 0, a, 0, size());
            for(int i=size();i<a.length;i++){
                a[i]=null;
            }
            return a;
        }
        @Override
        public boolean add(Integer e){
            Map.Entry<Integer, Integer> left_lr=treeMap.floorEntry(e);
            Map.Entry<Integer, Integer> right_lr=treeMap.higherEntry(e);
            if(left_lr!=null && e<left_lr.getKey()){
                return false;
            }
            boolean merge_l=left_lr!=null && left_lr.getValue().equals(e);
            boolean merge_r=right_lr!=null && e+1==right_lr.getKey();
            if(merge_l&&merge_r){
                treeMap.remove(right_lr.getKey());
                treeMap.put(left_lr.getKey(),right_lr.getValue());
            }else if(merge_l){
                treeMap.put(left_lr.getKey(),e+1);
            }else if(merge_r){
                treeMap.remove(right_lr.getKey());
                treeMap.put(e,right_lr.getValue());
            }else{
                treeMap.put(e,e+1);
            }
            size++;
            return true;
        }
        @Override
        public boolean remove(Object o){
            int e=(Integer)o;
            Map.Entry<Integer, Integer> lr=treeMap.floorEntry(e);
            if(lr==null||lr.getValue()<e){return false;}
            if(lr.getKey()==e&&lr.getValue()==e+1){
                treeMap.remove(e);
            }else if(lr.getKey()==e){
                treeMap.remove(e);
                treeMap.put(e+1,lr.getValue());
            }else if(lr.getValue()==e+1){
                treeMap.put(lr.getKey(),e);
            }else {
                treeMap.put(lr.getKey(),e);
                treeMap.put(e+1,lr.getValue());
            }
            size--;
            return true;
        }
        @Override
        public boolean containsAll(Collection<?> c){
            for(Object ci:c){
                if(!contains(ci)){return false;}
            }
            return true;
        }
        @Override
        public boolean addAll(Collection<? extends Integer> c){
            for(Integer ci:c){add(ci);}
            return !c.isEmpty();
        }
        @Override
        public boolean retainAll(Collection<?> c) {
            throw new UnsupportedOperationException("MEXSet::retailAll()");
        }
        @Override
        public boolean removeAll(Collection<?> c){
            for(Object ci:c){remove(ci);}
            return !c.isEmpty();
        }
        @Override
        public void clear(){
            treeMap.clear();
            size=0;
        }
        @Override
        public NavigableSet<Integer> descendingSet(){
            throw new UnsupportedOperationException("MEXSet::descendingSet()");
        }
        @Override
        public Iterator<Integer> descendingIterator(){
            return new Iterator<Integer>() {
                List<Pairintint> lrList;
                ListIterator<Pairintint> it;
                int left;
                int cursor;
                @Override
                public boolean hasNext() {
                    return left<cursor;
                }
                @Override
                public Integer next() {
                    int res=cursor;
                    step();
                    return res;
                }
                private void step(){
                    cursor--;
                    if(cursor<=left){
                        if(it.hasNext()){
                            Pairintint pii=it.next();
                            cursor=pii.second-1;
                            left=pii.first-1;
                        }
                    }
                }
                private Iterator<Integer> constructor(TreeMap<Integer,Integer> map){
                    lrList=new LinkedList<>();
                    map.forEach((l,r)->lrList.add(0,new Pairintint(l,r)));
                    it=lrList.listIterator();
                    left=0;cursor=0;
                    step();
                    return this;
                }
            }.constructor(treeMap);
        }
        @Override
        public NavigableSet<Integer> subSet(Integer fromElement, boolean fromInclusive, Integer toElement, boolean toInclusive){
            MEXSet res=new MEXSet();
            TreeMap<Integer,Integer> resmap=res.treeMap;
            treeMap.forEach((key, value)->{
                int l=max(key,fromElement+(fromInclusive?0:1));
                int r=min(value,toElement+(toInclusive?1:0));
                if(l<r){resmap.put(l,r);}
            });
            return res;
        }
        @Override
        public NavigableSet<Integer> headSet(Integer toElement, boolean inclusive){
            MEXSet res=new MEXSet();
            TreeMap<Integer,Integer> resmap=res.treeMap;
            treeMap.forEach((key, value)->{
                int l=key;
                int r=min(value,toElement+(inclusive?1:0));
                if(l<r){resmap.put(l,r);}
            });
            return res;
        }
        @Override
        public NavigableSet<Integer> tailSet(Integer fromElement, boolean inclusive){
            MEXSet res=new MEXSet();
            TreeMap<Integer,Integer> resmap=res.treeMap;
            treeMap.forEach((key, value)->{
                int l=max(key,fromElement+(inclusive?0:1));
                int r=value;
                if(l<r){resmap.put(l,r);}
            });
            return res;
        }
        @Override
        public Comparator<? super Integer> comparator(){
            return Comparator.naturalOrder();
        }
        @Override
        public SortedSet<Integer> subSet(Integer fromElement, Integer toElement){
            return subSet(fromElement,true,toElement,false);
        }
        @Override
        public SortedSet<Integer> headSet(Integer toElement) {
            return headSet(toElement,false);
        }
        @Override
        public SortedSet<Integer> tailSet(Integer fromElement) {
            return tailSet(fromElement,true);
        }
        @Override
        public Integer first(){
            return treeMap.firstKey();
        }
        @Override
        public Integer last(){
            Map.Entry<Integer,Integer> me=treeMap.lastEntry();
            return me==null?null:(me.getValue()-1);
        }
    }

    /**
     * 重心分解
     */
    static class CentroidsDecompose{
        int n;
        Collection<Integer>[] graph;
        int[] subsizes;
        int[] sizes2;
        boolean[] removeds;
        int[] parents;
        List<Integer> centroids;
        CentroidsDecompose(Collection<Integer>[] graph){
            this.n=graph.length;
            this.graph=graph;
            subsizes=new int[n];
            sizes2=new int[n];
            removeds=new boolean[n];
            parents=new int[n];
            centroids=new ArrayList<>(2);
        }
        public Pair<Integer,List<Integer>> findCentroid(int v){
            centroids.clear();
            //err.println(v+" "+sizes2[v]);
            int size=sizes2[v]==0?n:sizes2[v];
            List<Integer> res=new ArrayList<>();
            findCentroidR(v,size,-1);
            int center=centroids.get(0);
            for(int ch:graph[center]){if(!removeds[ch]){
                if(ch==parents[center]){
                    sizes2[ch]=size-subsizes[center];
                    res.add(ch);
                }else{
                    sizes2[ch]=subsizes[ch];
                    res.add(ch);
                }
            }}
            removeds[center]=true;
            return new Pair<>(center,res);
        }
        private void findCentroidR(int v,int size,int p){
            //err.printf("R %d %d %d\n",v,size,p);
            subsizes[v]=1;parents[v]=p;
            boolean ok=true;
            for(int ch:graph[v]){if(ch!=p&&!removeds[ch]){
                findCentroidR(ch,size,v);
                if(subsizes[ch]>size/2){ok=false;}
                subsizes[v]+=subsizes[ch];
            }}
            if(size-subsizes[v]>size/2){ok=false;}
            if(ok){centroids.add(v);}
        }
    }
    /**
     * 重軽分解 HL分解
     */
    static class HLDecompose{
        int n;
        Set<Integer>[] graph;
        int[] order;
        int[] parent;
        int[] size;
        int[] heavyChild;
        int[] root;
        Map<Integer,List<Integer>> result;
        HLDecompose(int n,Set<Integer>[] graph){
            this.n=n;
            this.graph=graph;
            order=new int[n];int oidx=0;
            parent=new int[n];Arrays.fill(parent,-2);
            Deque<Integer> dq=new ArrayDeque<>();
            dq.addLast(0);parent[0]=-1;
            while(!dq.isEmpty()){
                int hr=dq.pollFirst();
                order[oidx++]=hr;
                for(int nx:graph[hr]){if(parent[nx]==-2){
                    dq.addLast(nx);parent[nx]=hr;
                }}
            }
            size=new int[n];
            heavyChild=new int[n];
            for(int o=n-1;o>=0;o--){
                int node=order[o];
                int max=0;
                int maxi=-1;
                for(int child:graph[node]){if(parent[node]!=child){
                    size[node]+=size[child];
                    if(max<size[child]){
                        max=size[child];
                        maxi=child;
                    }
                }}
                size[node]++;
                heavyChild[node]=maxi;
            }
            root=new int[n];Arrays.fill(root,-1);
            result=new HashMap<>();
            for(int i=0;i<n;i++){
                if(root[i]==-1){
                    root[i]=i;
                    List<Integer> list=new ArrayList<>();
                    list.add(i);
                    result.put(i,list);
                }else{
                    result.get(root[i]).add(i);
                }
                if(heavyChild[i]!=-1){
                    root[heavyChild[i]]=root[i];
                }
            }
        }
    }
    /**
     * 強連結成分分解
     */
    static class StronglyConnectedComponents{
        private List<Integer> order2node;

        public int dagN;
        public Set<Integer>[] dagGraph;

        public Set<Integer>[] dagNode2gNodes;
        public int[] gNode2dagNode;

        void calc(Set<Integer>[] graph){
            Set<Integer>[] rgraph=graph_non_multi_edge(graph.length);
            IntStream.range(0,graph.length).forEach(
                    f->graph[f].forEach(t->rgraph[t].add(f))
            );
            calc(graph, rgraph);
        }
        void calc(Set<Integer>[] graph, Set<Integer>[] rgraph){
            int gN = graph.length;

            order2node=new ArrayList<>(gN);
            boolean[] vid=new boolean[gN];
            for(int node = 0; node< gN; node++){
                if(!vid[node]){dfs(node,graph,vid);}
            }

            gNode2dagNode=new int[gN];
            Arrays.fill(vid,false);
            dagN=0;
            for(int i = gN -1; i>=0; i--){
                int node=order2node.get(i);
                if(!vid[node]){dfs2(node,rgraph,vid);dagN++;}
            }
            dagNode2gNodes=graph_non_multi_edge(dagN);
            IntStream.range(0, gN).forEach(i->dagNode2gNodes[gNode2dagNode[i]].add(i));
            dagGraph=graph_non_multi_edge(dagN);
            IntStream.range(0, gN).forEach(
                    f->graph[f].forEach(t->{
                        if(gNode2dagNode[f]!=gNode2dagNode[t]){
                            dagGraph[gNode2dagNode[f]].add(gNode2dagNode[t]);
                        }
                    })
            );
        }
        private void dfs(int node,Set<Integer>[] graph,boolean[] vid){
            Deque<Integer> stack=new ArrayDeque<>();
            stack.addLast(node);
            vid[node]=true;
            while(!stack.isEmpty()){
                int hr=stack.pollLast();
                if(hr>=0){
                    stack.addLast(~hr);
                    for(int nx:graph[hr]){
                        if(!vid[nx]){
                            stack.addLast(nx);
                            vid[nx]=true;
                        }
                    }
                }else{
                    order2node.add(~hr);
                }
            }
        }
        private void dfs2(int node,Set<Integer>[] graph,boolean[] vid){
            Deque<Integer> stack=new ArrayDeque<>();
            stack.addLast(node);
            vid[node]=true;
            gNode2dagNode[node]=dagN;
            while(!stack.isEmpty()){
                int hr=stack.pollLast();
                for(int nx:graph[hr]){
                    if(!vid[nx]){
                        stack.addLast(nx);
                        vid[nx]=true;
                        gNode2dagNode[nx]=dagN;
                    }
                }
            }
        }
    }
    static <T> Set<T>[] graph_non_multi_edge(int n){
        Set<T>[] res=new Set[n];
        for(int i=0;i<n;i++){
            res[i]=new HashSet<>();
        }
        return res;
    }
    static <T> List<T>[] graph_multi_edge(int n){
        List<T>[] res=new List[n];
        for(int i=0;i<n;i++){
            res[i]=new ArrayList<>();
        }
        return res;
    }
    static void add_edge(Set[] graph,int u,int v,boolean direct,boolean one_indexed){
        if(one_indexed){
            u--;v--;
        }
        graph[u].add(v);
        if(!direct){
            graph[v].add(u);
        }
    }

    public static void print(int[] a, String head, String split, String tail, PrintWriter pw) {
        pw.print(head);
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                pw.print(split);
            }
            pw.print(a[i]);
        }
        pw.print(tail);
    }
    public static void print(long[] a, String head, String split, String tail, PrintWriter pw) {
        pw.print(head);
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                pw.print(split);
            }
            pw.print(a[i]);
        }
        pw.print(tail);
    }
    public static void print(double[] a, String head, String split, String tail, PrintWriter pw) {
        pw.print(head);
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                pw.print(split);
            }
            pw.printf("%.6f", a[i]);
            //pw.printf("%.12f", a[i]);
        }
        pw.print(tail);
    }
    public static void print(char[] a, String head, String split, String tail, PrintWriter pw) {
        pw.print(head);
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                pw.print(split);
            }
            pw.print(a[i]);
        }
        pw.print(tail);
    }
    public static void print(String[] a, String head, String split, String tail, PrintWriter pw) {
        pw.print(head);
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                pw.print(split);
            }
            pw.print(a[i]);
        }
        pw.print(tail);
    }
    public static void print(boolean[] a, String head, String split, String tail, PrintWriter pw) {
        pw.print(head);
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                pw.print(split);
            }
            pw.print(a[i]?'T':'F');
        }
        pw.print(tail);
    }
    public static void print(Object[] a, String head, String split, String tail, PrintWriter pw) {
        pw.print(head);
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                pw.print(split);
            }
            pw.print(a[i]);
        }
        pw.print(tail);
    }
    public static void print(List<?> l, String head, String split, String tail, PrintWriter pw) {
        if (l instanceof RandomAccess) {
            pw.print(head);
            if(!l.isEmpty()){
                pw.print(l.get(0));
            }
            for (int i = 1; i < l.size(); i++) {
                pw.print(split);
                pw.print(l.get(i));
            }
            pw.print(tail);
        } else {
            pw.print(head);
            ListIterator<?> lit = l.listIterator();
            if (lit.hasNext()) {
                pw.print(lit.next());
            }
            while (lit.hasNext()) {
                pw.print(split);
                pw.print(lit.next());
            }
            pw.print(tail);
        }
    }

    static char switchCase(char c){
        if(Character.isUpperCase(c)){return Character.toLowerCase(c);}
        if(Character.isLowerCase(c)){return Character.toUpperCase(c);}
        return c;
    }

    static int get(int[][] a, int i, int j) {
        return get(a,i,j,0);
    }
    static int get(int[][] a, int i, int j, int def) {
        try {
            return a[i][j];
        } catch (Exception e) {
            return def;
        }
    }
    static char get(String[] sa, int i, int j) {
        return get(sa,i,j,'#');
    }
    static char get(String[] sa, int i, int j, char def) {
        try {
            return sa[i].charAt(j);
        } catch (Exception e) {
            return def;
        }
    }
    static char get(StringBuilder[] sa, int i, int j) {
        return get(sa,i,j,(char)-1);
    }
    static char get(StringBuilder[] sa, int i, int j,char def) {
        try {
            return sa[i].charAt(j);
        } catch (Exception e) {
            return def;
        }
    }
    static boolean set(StringBuilder[] sa, int i, int j, char c) {
        if(i<0||sa.length<=i||j<0||sa[i].length()<=j){
            return false;
        }
        sa[i].setCharAt(j,c);
        return true;
    }
    static class Scnr {
        private final InputStream ins;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        Scnr() {this(System.in);}
        Scnr(InputStream in) {ins = in;}
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {buflen = ins.read(buffer);}
                catch (IOException e) {e.printStackTrace();}
                if (buflen <= 0) {return false;}
            }
            return true;
        }
        private int readByte() {
            if (hasNextByte()) {return buffer[ptr++];}
            else {return -1;}
        }

        private static boolean isPrintableChar_spaceOK(int c) {return 32 <= c && c <= 126;}
        public boolean hasNext_spaceOK() {
            while (hasNextByte() && !isPrintableChar_spaceOK(buffer[ptr])) {ptr++;}
            return hasNextByte();
        }
        public String nextLine() {return nextLineBuilder().toString();}
        public StringBuilder nextLineBuilder() {
            if (!hasNext_spaceOK()) {throw new NoSuchElementException();}
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar_spaceOK(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb;
        }


        private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) {ptr++;}
            return hasNextByte();
        }
        public String next() {return nextBuilder().toString();}
        public StringBuilder nextBuilder() {
            if (!hasNext()) {throw new NoSuchElementException();}
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb;
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
        public long nextLong() {
            if (!hasNext()) {throw new NoSuchElementException();}
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || Integer.MAX_VALUE < nl) {
                throw new NumberFormatException();
            }
            return (int) nl;
        }
        public StringBuilder[] nextABuilder(int n) {
            StringBuilder[] a = new StringBuilder[n];
            nextABuilder(a, n);
            return a;
        }
        public void nextABuilder(StringBuilder[] a, int n) {
            for (int i = 0; i < n; i++) {
                a[i] = nextBuilder();
            }
        }
        public void nextABuilder(StringBuilder[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextBuilder();
            }
        }
        public String[] nextA(int n) {
            String[] a = new String[n];
            nextA(a, n);
            return a;
        }
        public void nextA(String[] a, int n) {
            for (int i = 0; i < n; i++) {
                a[i] = next();
            }
        }
        public void nextA(String[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = next();
            }
        }
        public int[] nextAint(int n) {
            int[] a = new int[n];
            nextAint(a, n);
            return a;
        }
        public void nextAint(int[] a, int n) {
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
        }
        public void nextAint(int[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextInt();
            }
        }
        public Integer[] nextAInt(int n) {
            Integer[] a = new Integer[n];
            nextAInt(a, n);
            return a;
        }
        public void nextAInt(Integer[] a, int n) {
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
        }
        public void nextAInt(Integer[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextInt();
            }
        }
        public long[] nextAlong(int n) {
            long[] a = new long[n];
            nextAlong(a, n);
            return a;
        }
        public void nextAlong(long[] a, int n) {
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
        }
        public void nextAlong(long[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextLong();
            }
        }
        public Long[] nextALong(int n) {
            Long[] a = new Long[n];
            nextALong(a, n);
            return a;
        }
        public void nextALong(Long[] a, int n) {
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
        }
        public void nextALong(Long[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextLong();
            }
        }
        public double[] nextAdouble(int n) {
            double[] a = new double[n];
            nextAdouble(a, n);
            return a;
        }
        public void nextAdouble(double[] a, int n) {
            for (int i = 0; i < n; i++) {
                a[i] = nextDouble();
            }
        }
        public void nextAdouble(double[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextDouble();
            }
        }
        public Double[] nextADouble(int n) {
            Double[] a = new Double[n];
            nextADouble(a, n);
            return a;
        }
        public void nextADouble(Double[] a, int n) {
            for (int i = 0; i < n; i++) {
                a[i] = nextDouble();
            }
        }
        public void nextADouble(Double[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextDouble();
            }
        }
        public int[][] nextAAint(int h, int w) {
            int[][] aa = new int[h][w];
            nextAAint(aa, h, w);
            return aa;
        }
        public void nextAAint(int[][] aa, int h, int w) {
            for (int i = 0; i < h; i++) {
                nextAint(aa[i], 0, w);
            }
        }
        public void nextAAint(int[][] aa, int y, int h, int x, int w) {
            for (int i = y; i < y + h; i++) {
                nextAint(aa[i], x, w);
            }
        }
        public Integer[][] nextAAInt(int h, int w) {
            Integer[][] aa = new Integer[h][w];
            nextAAInt(aa, h, w);
            return aa;
        }
        public void nextAAInt(Integer[][] aa, int h, int w) {
            for (int i = 0; i < h; i++) {
                nextAInt(aa[i], 0, w);
            }
        }
        public void nextAAInt(Integer[][] aa, int y, int h, int x, int w) {
            for (int i = y; i < y + h; i++) {
                nextAInt(aa[i], x, w);
            }
        }
        public long[][] nextAAlong(int h, int w) {
            long[][] aa = new long[h][w];
            nextAAlong(aa, h, w);
            return aa;
        }
        public void nextAAlong(long[][] aa, int h, int w) {
            for (int i = 0; i < h; i++) {
                nextAlong(aa[i], 0, w);
            }
        }
        public void nextAAlong(long[][] aa, int y, int h, int x, int w) {
            for (int i = y; i < y + h; i++) {
                nextAlong(aa[i], x, w);
            }
        }
        public Long[][] nextAALong(int h, int w) {
            Long[][] aa = new Long[h][w];
            nextAALong(aa, h, w);
            return aa;
        }
        public void nextAALong(Long[][] aa, int h, int w) {
            for (int i = 0; i < h; i++) {
                nextALong(aa[i], 0, w);
            }
        }
        public void nextAALong(Long[][] aa, int y, int h, int x, int w) {
            for (int i = y; i < y + h; i++) {
                nextALong(aa[i], x, w);
            }
        }
        public double[][] nextAAdouble(int h, int w) {
            double[][] aa = new double[h][w];
            nextAAdouble(aa, h, w);
            return aa;
        }
        public void nextAAdouble(double[][] aa, int h, int w) {
            for (int i = 0; i < h; i++) {
                nextAdouble(aa[i], 0, w);
            }
        }
        public void nextAAdouble(double[][] aa, int y, int h, int x, int w) {
            for (int i = y; i < y + h; i++) {
                nextAdouble(aa[i], x, w);
            }
        }
        public Double[][] nextAADouble(int h, int w) {
            Double[][] aa = new Double[h][w];
            nextAADouble(aa, h, w);
            return aa;
        }
        public void nextAADouble(Double[][] aa, int h, int w) {
            for (int i = 0; i < h; i++) {
                nextADouble(aa[i], 0, w);
            }
        }
        public void nextAADouble(Double[][] aa, int y, int h, int x, int w) {
            for (int i = y; i < y + h; i++) {
                nextADouble(aa[i], x, w);
            }
        }
        public List<Integer> nextLInt(int n) {
            List<Integer> l = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                l.add(sc.nextInt());
            }
            return l;
        }
        public List<Long> nextLLong(int n) {
            List<Long> l = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                l.add(sc.nextLong());
            }
            return l;
        }
        public List<Double> nextLDouble(int n) {
            List<Double> l = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                l.add(sc.nextDouble());
            }
            return l;
        }
    }

    static PrintWriter nuls = new PrintWriter(
            new OutputStream() {
                public void write(int b) {}
                public void write(byte[] b) {}
                public void write(byte[] b, int off, int len) {}
                public void flush() {}
                public void close() {}
            }
    );
    static boolean onlineJudge;

    //static Scanner sc;
    static Scnr sc;
    static PrintWriter out;
    static PrintWriter err;

    static void YES(){out.println("YES");}
    static void Yes(){out.println("Yes");}
    static void yes(){out.println("yes");}
    static void NO(){out.println("NO");}
    static void No(){out.println("No");}
    static void no(){out.println("no");}
    static void YESNO(boolean b){if(b){YES();}else{NO();};}
    static void YesNo(boolean b){if(b){Yes();}else{No();};}
    static void yesno(boolean b){if(b){yes();}else{no();};}

    static int[][] dxy={
            { 1, 0}, { 0, 1}, {-1, 0}, { 0,-1},
            { 1, 1}, { 1,-1}, {-1, 1}, {-1,-1},
    };

    static char[] digit16 = {
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
            'A', 'B', 'C', 'D', 'E', 'F'
            //,'G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'
    };
    static long mod =
            //1_000_000_007L;
            998_244_353L;

    static int iMax = Integer.MAX_VALUE;
    static int iMin = Integer.MIN_VALUE;
    static long lMax = Long.MAX_VALUE;
    static long lMin = Long.MIN_VALUE;
    static double dMax = Double.POSITIVE_INFINITY;
    static double dMin = Double.NEGATIVE_INFINITY;

    public static void mainIO(String[] args, InputStream in, OutputStream os) {
        sc = new Scnr(in);
        out = new PrintWriter(os, true);
        err = new PrintWriter(System.err, true);
        try {
            //for(int i=sc.nextInt();i>0;i--)
            solve();
            out.flush();
            err.flush();
        } catch (Exception e) {
            out.flush();
            err.flush();
            throw e;
        }
    }
    public static void main(String[] args) {
        sc = new Scnr(System.in);
        //out = new PrintWriter(System.out, false); //true for Interactive
        out = new PrintWriter(System.out, true); //true for Interactive
        onlineJudge = "true".equals(System.getProperty("ONLINE_JUDGE"));
        err = onlineJudge ? nuls : new PrintWriter(System.err,true);
        try {
            plesolve();
            for(int i=sc.nextInt();i>0;i--)
            solve();
            out.flush();err.flush();
        } catch (Exception e) {
            out.flush();err.flush();
            throw e;
        }
    }
    static class RandoMap{
        Random random;
        Map<Integer,Integer> map;
        RandoMap(Random random){
            this.random=random;
            map=new HashMap<>();
        }
        public int map(int x){
            return map.computeIfAbsent(x,key-> random.nextInt(1_000_000_000));
        }
    }
    static class LinearSieve{
        int[] lpf;
        List<Integer> primes;
        int[] lpfcnt;
        int[] non_lpfs;
        LinearSieve(int n){
            lpf=new int[n+1];
            primes=new ArrayList<>();
            lpfcnt=new int[n+1];
            non_lpfs=new int[n+1];non_lpfs[1]=1;
            IntStream.rangeClosed(2,n).forEachOrdered(d->{
                if(lpf[d]==0){
                    lpf[d]=d;
                    primes.add(d);
                    lpfcnt[d]=1;
                    non_lpfs[d]=1;
                }
                for(int p:primes){
                    if(p*d>n || p>lpf[d]){break;}
                    lpf[p*d]=p;
                    lpfcnt[p*d]=(lpf[d]==p?lpfcnt[d]:0)+1;
                    non_lpfs[p*d]=(lpf[d]==p?non_lpfs[d]:d);
                }
            });
        }
        Map<Integer,Integer> pFacMap(int x){
            Map<Integer,Integer> res=new HashMap<>();
            //while(x>1){res.compute(lpf[x],(k,v)->(v==null?0:v)+1);x/=lpf[x];}
            while(x>1){res.put(lpf[x],lpfcnt[x]);x=non_lpfs[x];}
            return res;
        }
        int eulerPhi(int x){
            int res=1;
            while(x>1){res*=repow(lpf[x],lpfcnt[x]-1)*(lpf[x]-1);x=non_lpfs[x];}
            return res;
        }
    }
    static boolean in(int fromI,int x,int toE){return fromI<=x&&x<toE;}
    static boolean in(long fromI,long x,long toE){return fromI<=x&&x<toE;}
    static IntStream ISrange(int n){return ISrange(0,n);}
    static IntStream ISrange(int startInclusive,int endExclusive){return IntStream.range(startInclusive,endExclusive);}
    static void plesolve(){}

    static void solve(){
        /*
        要素数Nならスコアは0以上N-1以下

        平均下げ要員の個数を固定してスコアを最大化することを考える
        　平均下げ要員は当然下から順に選ぶ
        　スコア稼ぎ要員も下から取っていきたい　スコア稼ぎ要員によって平均が上がりスコアを稼げなくなったスコア稼ぎ要員はクビ
        これでO(N^2)

        クビにせず平均下げ要員に加えればよくない？

         */
        int n=sc.nextInt();
        int[] a=sc.nextAint(n);
        if(n<2){out.println(0);return;}
        Arrays.sort(a);

        int ans=0;

        long sum=a[0];
        int first=1;
        for(int i=1;i<n;i++){
            sum+=a[i];
            while(first<i+1 && a[first]*(i+1L)<=sum){
                first++;
            }
            //err.println(i+" "+first);
            ans=max(i+1-first,ans);
        }
        out.println(ans);
    }
}

//String keisen="*╶╷┌╴─┐┬╵└│├┘┴┤┼";
//String rail="┼┌─┐└│┘*";

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = next();
  while(q--)print(solve());
}

function solve(){
  var n = next();
  var a = nextssort(n);
  var sum = 0;
  for(var i = 0; i < n; i++){
    sum += a[i];
  }
  var ans = 0, l = n-1;
  for(var i = n-1; i > 0; i--){
    var ave = sum / (i+1);
    while(l >= 0 && a[l] > ave)l--;
    ans = Math.max(ans, i-l);
    sum -= a[i];
  }
  return ans;
}

Python solution:
t = int(input())

ans = []
import bisect
for _ in range(t):
    n = int(input())
    A = list(map(int, input().split()))

    A.sort()
    now = 0
    s = 0
    for k in range(n):
        s += A[k]
        idx = bisect.bisect_right(A, s/(k+1))
        cnt = max(0, k+1-idx)
        now = max(now, cnt)
    
    ans.append(now)
print(*ans, sep='\n')

Ruby solution:
gets.to_i.times do
  n=gets.to_i
  a=gets.split.map(&:to_i).sort
  s=0
  j=0
  ans=0
  c=0
  n.times do |i|
    s+=a[i]
    # p [a[j],(i+1),s]
    while j<n&&a[j]*(i+1)<=s
      j+=1
      # p [a[j],(i+1),s]
    end
    # p [i,i-j+1,a]
    if ans<i-j+1
      ans=i-j+1
    end
  end
  puts ans
end