import sequtils,algorithm,times,bitops template stopwatch(body) = (let t1 = cpuTime();body;stderr.writeLine "TIME:",(cpuTime() - t1) * 1000,"ms") proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "" ,discardable.} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord template useBinaryIndexedTree() = # 部分和検索 / 更新 O(log(N)) type BinaryIndexedTree[T] = ref object data: seq[T] # 引数以下の部分和(Fenwick Tree) proc initBinaryIndexedTree[T](n:int):BinaryIndexedTree[T] = new(result) result.data = newSeq[T](n) proc len[T](self:BinaryIndexedTree[T]): int = self.data.len() proc update[T](self:var BinaryIndexedTree[T],i:int,val:T) = var i = i while i < self.len(): self.data[i] += val i = i or (i + 1) proc `[]`[T](self:BinaryIndexedTree[T],i:int): T = var i = i while i >= 0: result += self.data[i] i = (i and (i + 1)) - 1 proc `$`[T](self:BinaryIndexedTree[T]): string = result = "[" for i in 0.. 100 : " ...]" else: "]") proc quicksort[A](xs: var seq[A],a,b:int) = proc pivot[A](xs: var seq[A],a,b:int): int = if xs.len < 2 : return 0 var pi = a let p = xs[pi] for i in a+1..b: if xs[i] >= p or pi >= i : continue swap(xs[i], xs[pi+1]) swap(xs[pi], xs[pi+1]) pi = pi + 1 return pi if b-a <= 1: return let p = pivot(xs,a,b) quicksort(xs, a , p) quicksort(xs, p+1 , b) proc deduplicated[T](arr: seq[T]): seq[T] = # require sorted result = @[] for a in arr: if result.len > 0 and result[^1] == a : continue result &= a useBinaryIndexedTree() stopwatch: let n = scan() var X = newSeq[int](n) var Y = newSeq[int](n) var Q = newSeq[int](n) var V = newSeq[int]() for i in 0..