#include using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,tuple&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} templateistream &operator>>(istream &is,array&a){for(auto&i:a)is>>i;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i template,std::nullptr_t> =nullptr,typename Func> T bin_search(T ok,T ng,const Func&f){ while(std::abs(ok-ng)>1){ T mid=(ok&ng)+((ok^ng)>>1); (f(mid)?ok:ng)=mid; } return ok; } template,int> loop=100,typename Func> T bin_search(T ok,T ng,const Func&f){ for(int i=0;i struct has_update_impl{ template static auto check(T&&x)->decltype(x.update(),std::true_type{}); template static auto check(...)->std::false_type; }; template struct has_update:public decltype(has_update_impl::check(std::declval())){}; template inline constexpr bool has_update_v=has_update::value; struct has_push_impl{ template static auto check(T&&x)->decltype(x.push(),std::true_type{}); template static auto check(...)->std::false_type; }; template struct has_push:public decltype(has_push_impl::check(std::declval())){}; template inline constexpr bool has_push_v=has_push::value; struct has_middle_impl{ template static auto check(T&&x)->decltype(x.middle,std::true_type{}); template static auto check(...)->std::false_type; }; template struct has_middle:public decltype(has_middle_impl::check(std::declval())){}; template inline constexpr bool has_middle_v=has_middle::value; template concept can_copy_monoid=requires(T x){ x.copy_monoid(std::declval()); }; template void splay(T*nd){ if constexpr(has_push_v&&!no_push)nd->push(); while(nd->par){ T *p=nd->par; T *pp=p->par; if constexpr(has_push_v&&!no_push){ if(pp)pp->push(); p->push(); nd->push(); } if(p->left==nd){ if(pp){ if(pp->left==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } pp->left=p->right; if(pp->left)pp->left->par=pp; p->left=nd->right; if(p->left)p->left->par=p; nd->right=p; p->par=nd; p->right=pp; pp->par=p; if constexpr(has_update_v){ if constexpr(can_copy_monoid)nd->copy_monoid(pp),pp->update(),p->update(); else pp->update(),p->update(),nd->update(); } continue; } else if(pp->right==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } p->left=nd->right; if(p->left)p->left->par=p; pp->right=nd->left; if(pp->right)pp->right->par=pp; nd->left=pp; pp->par=nd; nd->right=p; p->par=nd; if constexpr(has_update_v){ if constexpr(can_copy_monoid)nd->copy_monoid(pp),pp->update(),p->update(); else pp->update(),p->update(),nd->update(); } continue; } } nd->par=pp; if(pp){ if constexpr(has_middle_v){ if(pp->middle==p)pp->middle=nd; else if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } else{ if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } } p->left=nd->right; if(p->left)p->left->par=p; nd->right=p; p->par=nd; if constexpr(has_update_v){ if constexpr(can_copy_monoid)nd->copy_monoid(p),p->update(); else p->update(),nd->update(); } break; } else if(p->right==nd){ if(pp){ if(pp->left==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } p->right=nd->left; if(p->right)p->right->par=p; pp->left=nd->right; if(pp->left)pp->left->par=pp; nd->left=p; p->par=nd; nd->right=pp; pp->par=nd; if constexpr(has_update_v){ if constexpr(can_copy_monoid)nd->copy_monoid(pp),pp->update(),p->update(); else pp->update(),p->update(),nd->update(); } continue; } else if(pp->right==p){ nd->par=pp->par; if(pp->par){ if constexpr(has_middle_v){ if(pp->par->middle==pp)nd->par->middle=nd; else if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } else{ if(pp->par->left==pp)nd->par->left=nd; else if(pp->par->right==pp)nd->par->right=nd; } } pp->right=p->left; if(pp->right)pp->right->par=pp; p->right=nd->left; if(p->right)p->right->par=p; nd->left=p; p->par=nd; p->left=pp; pp->par=p; if constexpr(has_update_v){ if constexpr(can_copy_monoid)nd->copy_monoid(pp),pp->update(),p->update(); else pp->update(),p->update(),nd->update(); } continue; } } nd->par=pp; if(pp){ if constexpr(has_middle_v){ if(pp->middle==p)pp->middle=nd; else if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } else{ if(pp->left==p)pp->left=nd; else if(pp->right==p)pp->right=nd; } } p->right=nd->left; if(p->right)p->right->par=p; nd->left=p; p->par=nd; if constexpr(has_update_v){ if constexpr(can_copy_monoid)nd->copy_monoid(p),p->update(); else p->update(),nd->update(); } break; } else break; } } template [[nodiscard]]T* near(T *nd,decltype(T::key)k){ while(true){ if(kkey){ if constexpr(has_push_v)nd->push(); if(nd->left)nd=nd->left; else{ splay(nd); return nd; } } else if(nd->key)nd->push(); if(nd->right)nd=nd->right; else{ splay(nd); return nd; } } else{ splay(nd); return nd; } } return nullptr; } template [[nodiscard]]T* get_k(T *nd,decltype(T::sz)k){ while(true){ if constexpr(has_push_v)nd->push(); decltype(T::sz) lsz=nd->left?nd->left->sz:0; if(lsz==k)break; else if(kleft; else{ nd=nd->right; k-=1+lsz; } } splay(nd); return nd; } template [[nodiscard]]T* merge(T* l,T *r){ if(!l)return r; if(!r)return l; while(r->left){ if constexpr(has_push_v)r->push(); r=r->left; } if constexpr(has_push_v)r->push(); splay(r); r->left=l; l->par=r; if constexpr(has_update_v)r->update(); return r; } template [[nodiscard]]T* left_most(T*nd){ T nil; T *rnd=&nil; while(nd->left){ if constexpr(has_push_v)nd->push(); T *c=nd->left; if(!c->left){ rnd->left=nd; if constexpr(has_update_v||correct_parent)nd->par=rnd; rnd=rnd->left; nd=c; } else{ if constexpr(has_push_v)c->push(); nd->left=c->right; c->right=nd; if constexpr(has_update_v||correct_parent){ if(nd->left)nd->left->par=nd; nd->par=c; } if constexpr(has_update_v)nd->update(); if constexpr(has_update_v||correct_parent)c->par=rnd; rnd->left=c; nd=c->left; rnd=rnd->left; } } if constexpr(has_push_v)nd->push(); rnd->left=nd->right; nd->right=nil.left; nil.left=nil.right=nullptr; if constexpr(has_update_v||correct_parent){ if(rnd->left)rnd->left->par=rnd; if(nd->right)nd->right->par=nd; nd->par=nullptr; } if constexpr(has_update_v){ if(rnd!=&nil){ while(rnd){ rnd->update(); rnd=rnd->par; } } } return nd; } template [[nodiscard]]T* right_most(T*nd){ T nil; T *lnd=&nil; while(nd->right){ if constexpr(has_push_v)nd->push(); T *c=nd->right; if(!c->right){ lnd->right=nd; if constexpr(has_update_v||correct_parent)nd->par=lnd; lnd=lnd->right; nd=c; } else{ if constexpr(has_push_v)c->push(); nd->right=c->left; c->left=nd; if constexpr(has_update_v||correct_parent){ if(nd->right)nd->right->par=nd; nd->par=c; } if constexpr(has_update_v){ nd->update(); } if constexpr(has_update_v||correct_parent)c->par=lnd; lnd->right=c; nd=c->right; lnd=lnd->right; } } if constexpr(has_push_v)nd->push(); lnd->right=nd->left; nd->left=nil.right; nil.left=nil.right=nullptr; if constexpr(has_update_v||correct_parent){ if(lnd->right)lnd->right->par=lnd; if(nd->left)nd->left->par=nd; nd->par=nullptr; } if constexpr(has_update_v){ if(lnd!=&nil){ while(lnd){ lnd->update(); lnd=lnd->par; } } } return nd; } template struct DynamicSegmentTree{ private: using S=typename M::S; struct node{ node *left,*right,*par; I key; S v,sum; node(I key,S v):left(nullptr),right(nullptr),par(nullptr),key(key),v(v),sum(v){} void update(){ sum=v; if(left)sum=M::op(left->sum,sum); if(right)sum=M::op(sum,right->sum); } inline void copy_monoid(node *pp){sum=pp->sum;} ~node(){ if(left)delete left; if(right)delete right; } }; node *root; public: DynamicSegmentTree():root(nullptr){} void set(I key,S v){ if(!root){ root=new node(key,v); return; } root=near(root,key); if(root->key==key){ root->v=v; root->update(); } else{ node *nd=new node(key,v); if(keykey){ nd->left=root->left; if(nd->left)nd->left->par=nd; root->left=nd; nd->par=root; } else{ nd->right=root->right; if(nd->right)nd->right->par=nd; root->right=nd; nd->par=root; } nd->update(); root->update(); } } S get(I key){ if(!root)return M::e(); root=near(root,key); return root->key==key?root->v:M::e(); } S prod(I l,I r){ assert(l<=r); if(!root||l==r)return M::e(); root=near(root,l); S res=M::e(); if(l<=root->key&&root->keyv; if(root->right){ node *rnd=root->right; rnd->par=nullptr; rnd=near(rnd,r); if(rnd->left)res=M::op(res,rnd->left->sum); if(rnd->keyv); root->right=rnd; rnd->par=root; } return res; } S all_prod(){return root?root->sum:M::e();} void deallocate(){ if(root)delete root; } }; template::min()> struct MonoidMax{ using S=T; using F=std::nullptr_t; static inline S op(const S&x,const S&y){return x>n; vectora(n),b(n); cin>>a>>b; a.push_back(0); b.push_back(0); for(int i=n-1;i>=0;i--){ a[i]+=a[i+1]; b[i]+=b[i+1]; } auto eval=[&](int l,int r)->double { return (double)(a[l]-a[r])/(b[l]-b[r]); }; auto f=[&](double x){ DynamicSegmentTree>seg; vectorimos(n+1); for(int i=n;i>=0;i--){ double now=a[i]-x*b[i]; int mx=seg.prod(-1e200,now); if(i(1e18,0,f)<