import java.io.IOException; import java.io.InputStream; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; import java.util.NoSuchElementException; class SlidingQueue { class Pair { long v,cnt; public Pair(long v,long cnt) { this.v=v; this.cnt=cnt; } } int sz=0; Deque st=new ArrayDeque<>(); final long INF=Long.MAX_VALUE/3; void push(long v) { int cnt=1; while (!st.isEmpty() && st.peekLast().v <= v) { cnt+=st.peekLast().cnt; st.pollLast(); } st.addLast(new Pair(v,cnt)); ++sz; } void pop() { st.peekFirst().cnt--; if (st.peekFirst().cnt==0) st.pollFirst(); --sz; } long max() { if (st.isEmpty()) { return -INF; } else { return st.peekFirst().v; } } } public class Main { public static void main(String[] args) { new Main().run(); } final long MOD=(long)1e9+7; int MAX=1000000; long[] fac=new long[MAX]; long[] ifac=new long[MAX]; long[] inv=new long[MAX]; { fac[0]=fac[1]=ifac[0]=ifac[1]=inv[0]=inv[1]=1; for (int i=2;i