import sequtils,algorithm,math,tables import sets,intsets,queues,heapqueue,bitops,strutils 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 proc putchar_unlocked(c:char){. importc:"putchar_unlocked",header: "" .} proc printInt(a:int32) = if a == 0: putchar_unlocked('0') return template div10(a:int32) : int32 = cast[int32]((0x1999999A * cast[int64](a)) shr 32) template mod10(a:int32) : int32 = a - (a.div10 * 10) var n = a var rev = a var cnt = 0 while rev.mod10 == 0: cnt += 1 rev = rev.div10 rev = 0 while n != 0: rev = rev * 10 + n.mod10 n = n.div10 while rev != 0: putchar_unlocked((rev.mod10 + '0'.ord).chr) rev = rev.div10 while cnt != 0: putchar_unlocked('0') cnt -= 1 proc printInt(a:int,last:char) = a.int32.printInt() putchar_unlocked(last) template useBinaryHeap() = # 追加 / 最小値検索 / 最小値Pop O(log(N)) type BinaryHeap*[T] = ref object nodes: seq[T] compare: proc(x,y:T):int popchunk: bool proc newBinaryHeap*[T](compare:proc(x,y:T):int): BinaryHeap[T] = new(result) result.nodes = newSeq[T]() result.compare = compare proc compareNode[T](h:BinaryHeap[T],i,j:int):int = h.compare(h.nodes[i],h.nodes[j]) proc size*[T](h:BinaryHeap[T]):int = h.nodes.len() - h.popchunk.int proc items*[T](h:var BinaryHeap[T]):seq[T] = if h.popchunk : discard h.popimpl() return h.nodes proc top*[T](h:var BinaryHeap[T]): T = if h.popchunk : discard h.popimpl() return h.nodes[0] proc push*[T](h:var BinaryHeap[T],node:T):void = if h.popchunk : h.nodes[0] = node h.shiftdown() else: h.pushimpl(node) proc pop*[T](h:var BinaryHeap[T]):T = if h.popchunk: discard h.popimpl() h.popchunk = true return h.nodes[0] proc shiftdown[T](h:var BinaryHeap[T]): void = h.popchunk = false let size = h.nodes.len() var i = 0 while true : let L = i * 2 + 1 let R = i * 2 + 2 if L >= size : break let child = if R < size and h.compareNode(R,L) <= 0 : R else: L if h.compareNode(i,child) <= 0: break swap(h.nodes[i],h.nodes[child]) i = child proc pushimpl[T](h:var BinaryHeap[T],node:T):void = h.nodes.add(node) #末尾に追加 var i = h.nodes.len() - 1 while i > 0: # 末尾から木を整形 let parent = (i - 1) div 2 if h.compare(h.nodes[parent],node) <= 0: break h.nodes[i] = h.nodes[parent] i = parent h.nodes[i] = node proc popimpl[T](h:var BinaryHeap[T]):T = result = h.nodes[0] # rootと末尾を入れ替えて木を整形 h.nodes[0] = h.nodes[^1] h.nodes.setLen(h.nodes.len() - 1) h.shiftdown() useBinaryHeap() proc solve() : int = let n = scan() let L = newSeqWith(n,scan()).sorted(cmp) var R = @[1] for i in 1..