import sequtils,algorithm template times*(n:int,body) = (for _ in 0.." .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': break result = 10 * result + k.ord - '0'.ord type HeapQueue*[T] = object ## A heap queue, commonly known as a priority queue. data: seq[T] proc initHeapQueue*[T](): HeapQueue[T] = ## Create a new empty heap. discard proc len*[T](heap: HeapQueue[T]): int {.inline.} = ## Return the number of elements of `heap`. heap.data.len proc `[]`*[T](heap: HeapQueue[T], i: Natural): T {.inline.} = ## Access the i-th element of `heap`. heap.data[i] proc heapCmp[T](x, y: T): bool {.inline.} = return (x < y) proc siftdown[T](heap: var HeapQueue[T], startpos, p: int) = ## 'heap' is a heap at all indices >= startpos, except possibly for pos. pos ## is the index of a leaf with a possibly out-of-order value. Restore the ## heap invariant. var pos = p var newitem = heap[pos] # Follow the path to the root, moving parents down until finding a place # newitem fits. while pos > startpos: let parentpos = (pos - 1) shr 1 let parent = heap[parentpos] if heapCmp(newitem, parent): heap.data[pos] = parent pos = parentpos else: break heap.data[pos] = newitem proc siftup[T](heap: var HeapQueue[T], p: int) = let endpos = len(heap) var pos = p let startpos = pos let newitem = heap[pos] # Bubble up the smaller child until hitting a leaf. var childpos = 2*pos + 1 # leftmost child position while childpos < endpos: # Set childpos to index of smaller child. let rightpos = childpos + 1 if rightpos < endpos and not heapCmp(heap[childpos], heap[rightpos]): childpos = rightpos # Move the smaller child up. heap.data[pos] = heap[childpos] pos = childpos childpos = 2*pos + 1 # The leaf at pos is empty now. Put newitem there, and bubble it up # to its final resting place (by sifting its parents down). heap.data[pos] = newitem siftdown(heap, startpos, pos) proc push*[T](heap: var HeapQueue[T], item: T) = ## Push `item` onto heap, maintaining the heap invariant. heap.data.add(item) siftdown(heap, 0, len(heap)-1) proc pop*[T](heap: var HeapQueue[T]): T = ## Pop and return the smallest item from `heap`, ## maintaining the heap invariant. let lastelt = heap.data.pop() if heap.len > 0: result = heap[0] heap.data[0] = lastelt siftup(heap, 0) else: result = lastelt proc solve() : int = let n = scan() var L = newSeq[int](n) for i in 0..