using System; using System.Collections; using System.Collections.Generic; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ PriorityQueue PQ=new PriorityQueue(); for(int i=0;iint.Parse(e));} static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));} static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));} } class Pair:IComparable{ public double len; public int idx; public Pair(double l_,int i_){ len=l_;idx=i_; } public int CompareTo(Pair y){ return this.len>y.len?1:this.len where T:IComparable{ //T:IComparable //IComparerかComparisonを指定してインスタンス化する事も可 //引数なしインスタンス化⇒ComparedToで比較 //大きいものほどTopへ enum typeCompare{ isIComparerable=1, useIComparer=2, useDComparison=3 } List buffer; typeCompare tComp; IComparer Cmper; Comparison Cmp; public PriorityQueue(IComparer comparer_){ this.buffer=new List(); tComp=typeCompare.useIComparer; Cmper=comparer_; Cmp=null; } public PriorityQueue(){ this.buffer=new List(); tComp=typeCompare.isIComparerable; } public PriorityQueue(Comparison cmp_){ this.buffer=new List(); tComp=typeCompare.useDComparison; Cmp=cmp_; Cmper=null; } public PriorityQueue(int capacity,IComparer comparer_){ this.buffer=new List(capacity); tComp=typeCompare.useIComparer; Cmper=comparer_; } public PriorityQueue(int capacity){ this.buffer=new List(capacity); tComp=typeCompare.isIComparerable; } public PriorityQueue(int capacity,Comparison cmp_){ this.buffer=new List(capacity); tComp=typeCompare.useDComparison; Cmp=cmp_; } void PushHeap(List arr,T elem){ int n=arr.Count; buffer.Add(elem); if(tComp==typeCompare.isIComparerable){ try{ while(n!=0){ int i=(n-1)/2; if(arr[n].CompareTo(arr[i]) > 0){ T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp; } n=i; } } catch (Exception e){ Console.WriteLine("{0} Exception caught.", e); } }else if(tComp==typeCompare.useIComparer){ try{ while(n!=0){ int i=(n-1)/2; if(Cmper.Compare(arr[n],arr[i]) > 0){ T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp; } n=i; } } catch (Exception e){ Console.WriteLine("{0} Exception caught.", e); } }else if(tComp==typeCompare.useDComparison){ while(n!=0){ int i=(n-1)/2; if(Cmp(arr[n],arr[i]) > 0){ T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp; } n=i; } } } void PopHeap(List arr){ int n=arr.Count - 1; arr[0] = arr[n]; arr.RemoveAt(n); if(tComp==typeCompare.isIComparerable){ for (int i=0,j;(j = 2*i +1)