i      !"# !" !"$%&' ()*+,$%&'$%&' -./A function of type  a is used as if it were (0) for comparison purposes.  This function must be a total ordering. &A range min function. Given an index i and a length m, returns the  minimum element in the range i..i+m-1. $The type of the length of a vector. 1QThe type for which this package provides a specialized range-min implementation. The type of a vector index. 2345 -./12345 -.//123456789:;<=>?@ABCDEFG :;<=>?@ACDEFG :;;<=>?@ACDEFG HIJKLMNOPQRSTUVWHIJKLMNOPQRSTUVWHIJKLMNOPQRSTUVW XYZ[\]^_`abcdefgXYZ[\]^_`abc XYZ[\]^_`abc $hijklmnopqrstuvwxyz{|}~$hijklmnopqrstuvwxyz{|}~$hijklmnopqrstuvwxyz{|}~   A 3 is a tree, specified in the following format: the  i-th entry of the vector is the parent of node i, or is -1 for the  root. O(n)Q. Given a comparison function and a lookup function, this function constructs a   2 with the property that the minimum index between i and j ? in the result vector is the same as the minimum index between i and j from the original I elements. (In both cases, ties are broken by which index comes first.) BThis allows us to use the specialized range-min implementation on  ,  even for other f= implementations, other element types, and other comparison  functions. MInternally, this function constructs the Cartesian tree of the input vector N (implicitly, to save memory and stack space), and returns the vector of the $ depth of each element in the tree. FThis method takes as input a tree, specified as an array in which the  ith entry is the parent of node i, or -1 for the root. It returns ( the vector of the depths of each node. 8This method constructs the cartesian tree of the input.  A type is an instance of 0 if it has a natural order-preserving injection  into , typically but not always . Functions like rangeMin and  unsafeVecRangeMax which use the element type',s natural ordering may be auto-specialized  when the element type is an  instance. 1()*+,defg !"$%&'-./12345XYZ[\]^_`abcThis implements the  O(n log n)' range-min algorithm, which explicitly I precomputes the answer to every range-min query with size a power of 2. This implements the O(n) precomputation, O(log n) query algorithm. . It precomputes block-mins for blocks of size log n \ 2/ , uses the   O(n log n)< algorithm for multi-block queries, and explicitly computes  internal block queries. !This implements the brute-force, O(n^2)- DP algorithm that precomputes the answer to  every range-min query explicitly.  There are  n n distinct binary trees of size n.  A value of type % is the index of a particular binary  tree in the range 0.. n n - 1. O(n)M. Returns a range-min function on the vector, under the natural ordering of . ( This function can be, depending on the f implementation, three to four  times as fast as  (0).  Example:     ( [0,7,-10,4,5,4] ) 0 6 == 2   ( [0,7,-10,4,5,4] ) 2 3 == 2   ( [0,7,-10,4,5,4] ) 3 3 == 3 The returned function does not do bounds checks. If n is the length of the vector,  and i and m are passed as arguments to the  , then if i < 0, m < 1, or   i + m > n, a segfault may occur.  A vector of s. 1A range-min function on the vector which runs in O(1). O(n)L. Returns a range-min function on the vector, with the natural ordering of . ( This function can be, depending on the f implementation, three to four  times as fast as   (0). Equivalent to $, except that the returned function does do bounds checks. , When it receives a bad query, it throws an .  A vector of s. 1A range-min function on the vector which runs in O(1). O(n)M. Returns a range-min function on the vector, under the specified ordering.  The returned function does not do bounds checks; see  for details.  Example:  ! -- Finding the element with the largest absolute value in a subrange.   (\ i j ->  i   j) ( [0,7,-10,4,5,4] ) 0 6 == 2   (\ i j ->  i   j) ( [0,7,-10,4,5,4] ) 2 3 == 2   (\ i j ->  i   j) ( [0,7,-10,4,5,4] ) 3 3 == 4 A total ordering on the type a. A vector of elements of type a. 1A range-min function on the vector which runs in O(1). O(n). Equivalent to  (0) . Specialized for instances of .  The returned function does not do bounds checks; see  for details.  Example:  7 -- In reality, these would be rewritten into calls to , since  is an  -- instance of .    ( "banana" ) 0 6 == 1    ( "banana" ) 1 1 == 1    ( "banana" ) 3 3 == 3 A vector of elements of type a. 2A range-min function (under the natural ordering)  on the vector which runs in O(1). O(n). Equivalent to  () . Specialized for instances of .  The returned function does not do bounds checks; see  for details.  Example:  7 -- In reality, these would be rewritten into calls to , since   -- is an instance of .    ( "banana" ) 0 6 == 2    ( "banana" ) 1 1 == 1    ( "banana" ) 3 3 == 4 A vector of elements of type a. 2A range-max function (under the natural ordering)  on the vector which runs in O(1). O(n)M. Returns a range-min function on the vector, under the specified ordering.  The returned function does do bounds checks; see  for details. A total ordering on the type a. A vector of elements of type a. 1A range-min function on the vector which runs in O(1). O(n). Equivalent to   (0); a safer version of  .  Specialized for instances of . The returned function does do bounds checks;  see  for details. A vector of elements of type a. 2A range-min function (under the natural ordering)  on the vector which runs in O(1). O(n). Equivalent to   (); a safer version of  .  Specialized for instances of . The returned function does do bounds checks;  see  for details. A vector of elements of type a. 2A range-max function (under the natural ordering)  on the vector which runs in O(1). O(n).  (< =?) n look is equivalent to   (<=?) ( n look).  The returned function does not do bounds checks; see  for details. A total ordering on the type a. $The number of elements to generate. 2A function to generate the element at each index. 3A range-min function on the elements which runs in O(1). O(n). Equivalent to  (0) . Specialized for instances of .  The returned function does not do bounds checks; see  for details. $The number of elements to generate. 2A function to generate the element at each index. DA range-min function on the elements (under their natural ordering)  which runs in O(1). O(n). Equivalent to  () . Specialized for instances of .  The returned function does not do bounds checks; see  for details. $The number of elements to generate. 2A function to generate the element at each index. DA range-max function on the elements (under their natural ordering)  which runs in O(1). O(n).  (< =?) n look is equivalent to    (<=?) ( n look), and is a safer version of   (< =?) n look. The returned function does do bounds checks; see   for details. A total ordering on the type a. $The number of elements to generate. 2A function to generate the element at each index. 3A range-min function on the elements which runs in O(1). O(n). Equivalent to  (0), and a safer version of .  Specialized for instances of .  The returned function does do bounds checks; see  for details. $The number of elements to generate. 2A function to generate the element at each index. DA range-min function on the elements (under their natural ordering)  which runs in O(1). O(n). Equivalent to  (), and a safer version of .  Specialized for instances of .  The returned function does do bounds checks; see  for details. $The number of elements to generate. 2A function to generate the element at each index. DA range-max function on the elements (under their natural ordering)  which runs in O(1). O(n).  inject xs is equivalent to   (\ x y -> inject x 0 inject y) xs!, but is frequently much faster, > fusing with the input vector and converting it directly to a  .  The returned function does not do bounds checks; see  for details. O(n).  inject xs is equivalent to    (\ x y -> inject x 0 inject y) xs!, but is frequently much faster, > fusing with the input vector and converting it directly to a  .  The returned function does do bounds checks; see  for details.    $Labels a tree in depth-first order. ]Takes a tree and indexes it in depth-first order, returning the number of nodes, the indexed 0 tree, and the lowest common ancestor function.  n ix tree( takes a tree whose nodes are mapped by  ix to a unique index in the range 0..n-1, and returns a function N which takes two indices (corresponding to two nodes in the tree) and returns  the label of their lowest common ancestor.  This takes O(n)& preprocessing and answers queries in O(1), as it is an  application of  Data.RangeMin. !For binary trees, consider using Data.RangeMin.LCA.Binary.  A generic binary tree. WTakes a binary tree and indexes it inorder, returning the number of nodes, the indexed 0 tree, and the lowest common ancestor function.  Similar to LCA.lowestCommonAncestor>, but optimized for binary trees. This method can reasonably % be expected to run twice as fast as lowestCommonAncestor.  !"#$%&'()*+,-.//0123456789:;<=>?@>?A>?B>?C>?DEFF>GHIJKLMNOPQRRSTUVWXYZ[\]^ _ R S ` a b c d e V f g h ] ^ W i j k l m n o p q r s tuvwuxyuxzu{| } ~  S c d b a g V f e h ^ W FFuz>))))u>>>Gubrangemin-2.2.1 Data.RangeMinData.RangeMin.CartesianData.RangeMin.LCAData.RangeMin.LCA.BinaryData.RangeMin.Common.Math Data.RangeMin.Common.CombinatorsData.RangeMin.Common.Types#Data.RangeMin.Fusion.Stream.MonadicData.RangeMin.Fusion.StreamData.RangeMin.Common.VectorData.RangeMin.Fusion*Data.RangeMin.Int.Linearithmic.Combinators%Data.RangeMin.Int.Catalan.CombinatorsData.RangeMin.Int.Catalan.TableData.RangeMin.LCA.IndexMData.RangeMin.Cartesian.SpecData.RangeMin.CommonData.RangeMin.Int.LinearithmicData.RangeMin.Int.NearLinearData.RangeMin.Int.QuadraticData.RangeMin.Int.CatalanData.RangeMin.Int.LinearLEqRangeMinLengthIndex equivVectorBy InjectiveunsafeIntRangeMin intRangeMinunsafeVecRangeMinByunsafeVecRangeMinunsafeVecRangeMax vecRangeMinBy vecRangeMin vecRangeMaxunsafeRangeMinByunsafeRangeMinunsafeRangeMax rangeMinByrangeMinrangeMaxunsafeInjectRangeMininjectRangeMinquickLCAlowestCommonAncestorBinTreeTipquickLCABinary lcaBinarydiv'mod'bit'bitWceilLogintLogwordLogon<$>.:uncurry'base Control.MonadliftM3liftM2liftMunlesswhenRMIP GHC.Classes<=ValueVVectorPVectortoRMrunRMStepYieldLastDoneStreamlength iunfoldMNimapMimapM_cap generateMconsumesnocMifoldlM imapAccumLMunbox fromListNMStream liftStreamimapgenerateenumNenumNRiunfoldNsnoc imapAccumLifoldlvlength unsafeFreezesliceMwritereadnewnewWithdropsliceminIndex!getRowvector-0.6.0.2Data.Vector.GenericcreateData.Vector.Generic.BaseMutableVectorData.Vector.Generic.MutableMVectorconvertunstreamstreamistreamunzipunzip3streamRstreamIRmap ipostscanliterateN mapAccumL unsafeUpdatemapM_ postscanl replicatesnoc'unfoldNfoldlunsafeBackpermute munstream replicateMfillMfill buildRowsUnf equivClassesmaxLogcatalanscatalanIndexM runIndexMgetIndex execIndexMSILNil CartesianTreeData.Vector.Primitiveghc-prim GHC.TypesInt makeDepthsmakeTreeGHC.EnumfromEnuminjectequivVectorMinequivVectorMax invertVector invertValueequivMapequivInjectorMinequivInjectorMaxn2Cross nlognCross nearNCross forceBlockN2 forceNLogNforceBlockMins buildTablePpIx_pVal explicitRMQ quadTableCCatType:<catalanIndexer negativeStartnonPositiveWidthoutOfBoundsQuery checkBoundsinternalIntRangeMinfromListGHC.IO.ExceptionArrayExceptionGHC.Numabs>=Char Data.VectorTravDepthdfOrdertravelD unfoldBin inorderBininorderD