using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ List Bottom = new List(); List L = new List(); List R = new List(); Bottom.Add(new Q(0,1+0)); L.Add(new Q(1,1+0)); R.Add(new Q(1,1+0)); for(int i=0;i1){ c = (r+l)/2; if(Bottom[c] < uh){ l = c; }else{ r = c; } } //Console.WriteLine("le:{0},re:{1},l;{2}",le,re,l); ans += l+1; } } Console.WriteLine(ans); } int N; long[] P,A,B; public Sol(){ N = ri(); P = new long[N]; A = new long[N]; B = new long[N]; for(int i=0;iint.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} } struct Q:IComparable { long num; long den; public static long gcd(long a,long b){ return a==0?b:gcd(b%a,a); } public static Q Red(Q x){ long n=x.Num; long d=x.Den; long g=gcd(Math.Abs(n),Math.Abs(d)); n/=g; d/=g; if(d<0){n*=-1;d*=-1;} return new Q(n,d); } public int CompareTo(Q t){ var d = num*t.den-den*t.num; return d > 0 ? 1 : d < 0 ? -1 : 0; } public long Num{ get{return num;} set{this.num=value;} } public long Den{ get{return den;} set{this.den=value;} } public Q(long n_,long d_){ num=n_;den=d_; } public static implicit operator Q(long n){ return new Q(n,1); } public static Q operator+(Q a,Q b){ return Red(new Q(a.Num*b.Den+a.Den*b.Num,a.Den*b.Den)); } public static Q operator-(Q a,Q b){ return Red(new Q(a.Num*b.Den-a.Den*b.Num,a.Den*b.Den)); } public static Q operator-(Q a){ return Red(new Q(-a.Num,a.Den)); } public static Q operator*(Q a,Q b){ return Red(new Q(a.Num*b.Num,a.Den*b.Den)); } public static Q operator/(Q a,Q b){ return Red(new Q(a.Num*b.Den,a.Den*b.Num)); } public static bool operator>(Q a,Q b){ return a.CompareTo(b) > 0; } public static bool operator<(Q a,Q b){ return a.CompareTo(b) < 0; } public static bool operator>=(Q a,Q b){ return a.CompareTo(b) >= 0; } public static bool operator<=(Q a,Q b){ return a.CompareTo(b) <= 0; } public static Q Min(Q a,Q b){ return a < b ? a : b; } public override String ToString(){ return this.Num.ToString()+"/"+this.Den.ToString(); } }