import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2]) {.checks: off.} ImportExpand "cplib/tmpl/citrus.nim" <=== "when not declared CPLIB_TMPL_CITRUS:\n const CPLIB_TMPL_CITRUS* = 1\n {.warning[UnusedImport]: off.}\n {.hint[XDeclaredButNotUsed]: off.}\n import os\n import algorithm\n import sequtils\n import tables\n import macros\n import std/math\n import sets\n import strutils\n import strformat\n import sugar\n import streams\n import deques\n import bitops\n import heapqueue\n import options\n const MODINT998244353* = 998244353\n const MODINT1000000007* = 1000000007\n const INF* = 100100111\n const INFL* = int(3300300300300300491)\n type double* = float64\n let readNext = iterator(getsChar: bool = false): string {.closure.} =\n while true:\n var si: string\n try: si = stdin.readLine\n except EOFError: yield \"\"\n for s in si.split:\n if getsChar:\n for i in 0.. x: result -= 1)\n proc `^`*(x: SomeInteger, y: SomeInteger): int = x xor y\n proc `&`*(x: SomeInteger, y: SomeInteger): int = x and y\n proc `|`*(x: SomeInteger, y: SomeInteger): int = x or y\n proc `>>`*(x: SomeInteger, y: SomeInteger): int = x shr y\n proc `<<`*(x: SomeInteger, y: SomeInteger): int = x shl y\n proc `%=`*(x: var SomeInteger, y: SomeInteger): void = x = x % y\n proc `//=`*(x: var SomeInteger, y: SomeInteger): void = x = x // y\n proc `^=`*(x: var SomeInteger, y: SomeInteger): void = x = x ^ y\n proc `&=`*(x: var SomeInteger, y: SomeInteger): void = x = x & y\n proc `|=`*(x: var SomeInteger, y: SomeInteger): void = x = x | y\n proc `>>=`*(x: var SomeInteger, y: SomeInteger): void = x = x >> y\n proc `<<=`*(x: var SomeInteger, y: SomeInteger): void = x = x << y\n proc `[]`*(x, n: int): bool = (x and (1 shl n)) != 0\n proc `[]=`*(x: var int, n: int, i: bool) =\n if i: x = x or (1 << n)\n else: (if x[n]: x = x xor (1 << n))\n proc pow*(a, n: int, m = INFL): int =\n var\n rev = 1\n a = a\n n = n\n while n > 0:\n if n % 2 != 0: rev = (rev * a) mod m\n if n > 1: a = (a * a) mod m\n n >>= 1\n return rev\n proc sqrt*(x: int): int =\n assert(x >= 0)\n result = int(sqrt(float64(x)))\n while result * result > x: result -= 1\n while (result+1) * (result+1) <= x: result += 1\n proc chmax*[T](x: var T, y: T): bool {.discardable.} = (if x < y: (x = y; return true; ) return false)\n proc chmin*[T](x: var T, y: T): bool {.discardable.} = (if x > y: (x = y; return true; ) return false)\n proc `max=`*[T](x: var T, y: T) = x = max(x, y)\n proc `min=`*[T](x: var T, y: T) = x = min(x, y)\n proc at*(x: char, a = '0'): int = int(x) - int(a)\n converter tofloat*(n: int): float = float(n)\n proc Yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n proc No*(b: bool = true): void = Yes(not b)\n proc YES_upper*(b: bool = true): void = print(if b: \"YES\" else: \"NO\")\n proc NO_upper*(b: bool = true): void = Yes_upper(not b)\n const DXY* = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n const DDXY* = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]\n macro exit*(statement: untyped): untyped = (quote do: (`statement`; quit()))\n" ImportExpand "atcoder/lazysegtree.nim" <=== "when not declared ATCODER_LAZYSEGTREE_HPP:\n const ATCODER_LAZYSEGTREE_HPP* = 1\n \n #[ import atcoder/internal_bit ]#\n when not declared ATCODER_INTERNAL_BITOP_HPP:\n const ATCODER_INTERNAL_BITOP_HPP* = 1\n import std/bitops\n \n #ifdef _MSC_VER\n #include \n #endif\n \n # @param n `0 <= n`\n # @return minimum non-negative `x` s.t. `n <= 2**x`\n proc ceil_pow2*(n:SomeInteger):int =\n var x = 0\n while (1.uint shl x) < n.uint: x.inc\n return x\n # @param n `1 <= n`\n # @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`\n proc bsf*(n:SomeInteger):int =\n return countTrailingZeroBits(n)\n #[ import atcoder/rangeutils ]#\n when not declared ATCODER_RANGEUTILS_HPP:\n const ATCODER_RANGEUTILS_HPP* = 1\n type RangeType* = Slice[int] | HSlice[int, BackwardsIndex] | Slice[BackwardsIndex]\n type IndexType* = int | BackwardsIndex\n template halfOpenEndpoints*(p:Slice[int]):(int,int) = (p.a, p.b + 1)\n template `^^`*(s, i: untyped): untyped =\n (when i is BackwardsIndex: s.len - int(i) else: int(i))\n template halfOpenEndpoints*[T](s:T, p:RangeType):(int,int) =\n (s^^p.a, s^^p.b + 1)\n import std/sequtils\n import std/algorithm\n {.push inline.}\n type LazySegTree*[S,F;p:static[tuple]] = object\n len*, size*, log*:int\n d*:seq[S]\n lz*:seq[F]\n\n template calc_op*[ST:LazySegTree](self:ST or typedesc[ST], a, b:ST.S):auto =\n block:\n let u = ST.p.op(a, b)\n u\n template calc_e*[ST:LazySegTree](self:ST or typedesc[ST]):auto =\n block:\n let u = ST.p.e()\n u\n template calc_mapping*[ST:LazySegTree](self:ST or typedesc[ST], a:ST.F, b:ST.S):auto =\n block:\n let u = ST.p.mapping(a, b)\n u\n template calc_composition*[ST:LazySegTree](self:ST or typedesc[ST], a, b:ST.F):auto =\n block:\n # こう書かないとバグる事象を検出\n let u = ST.p.composition(a, b)\n u\n template calc_id*[ST:LazySegTree](self:ST or typedesc[ST]):auto =\n block:\n let u = ST.p.id()\n u\n\n proc update[ST:LazySegTree](self:var ST, k:int) =\n self.d[k] = ST.calc_op(self.d[2 * k], self.d[2 * k + 1])\n proc all_apply*[ST:LazySegTree](self:var ST, k:int, f:ST.F) =\n self.d[k] = ST.calc_mapping(f, self.d[k])\n if k < self.size:\n self.lz[k] = ST.calc_composition(f, self.lz[k])\n proc all_apply*[ST:LazySegTree](self:var ST, f:ST.F) =\n self.all_apply(1, f)\n proc push*[ST:LazySegTree](self: var ST, k:int) =\n self.all_apply(2 * k, self.lz[k])\n self.all_apply(2 * k + 1, self.lz[k])\n self.lz[k] = ST.calc_id()\n\n proc init[ST:LazySegTree](self:var ST, v:seq[ST.S]) =\n let\n n = v.len\n log = ceil_pow2(n)\n size = 1 shl log\n (self.len, self.size, self.log) = (n, size, log)\n if self.d.len < 2 * size:\n self.d = newSeqWith(2 * size, ST.calc_e())\n else:\n self.d.fill(0, 2 * size - 1, ST.calc_e())\n for i in 0.. int max_right(int l) {\n# return max_right(l, [](S x) { return g(x); });\n# }\n proc max_right*[ST:LazySegTree](self:var ST, l:IndexType, g:proc(s:ST.S):bool):int =\n var l = self^^l\n assert l in 0..self.len\n assert g(ST.calc_e())\n if l == self.len: return self.len\n l += self.size\n for i in countdown(self.log, 1): self.push(l shr i)\n var sm = ST.calc_e()\n while true:\n while l mod 2 == 0: l = l shr 1\n if not g(ST.calc_op(sm, self.d[l])):\n while l < self.size:\n self.push(l)\n l = (2 * l)\n if g(ST.calc_op(sm, self.d[l])):\n sm = ST.calc_op(sm, self.d[l])\n l.inc\n return l - self.size\n sm = ST.calc_op(sm, self.d[l])\n l.inc\n if not((l and -l) != l): break\n return self.len\n\n# template int min_left(int r) {\n# return min_left(r, [](S x) { return g(x); });\n# }\n proc min_left*[ST:LazySegTree](self: var ST, r:IndexType, g:proc(s:ST.S):bool):int =\n var r = self^^r\n assert r in 0..self.len\n assert(g(ST.calc_e()))\n if r == 0: return 0\n r += self.size\n for i in countdown(self.log, 1): self.push((r - 1) shr i)\n var sm = ST.calc_e()\n while true:\n r.dec\n while r > 1 and r mod 2 == 1: r = r shr 1\n if not g(ST.calc_op(self.d[r], sm)):\n while r < self.size:\n self.push(r)\n r = (2 * r + 1)\n if g(ST.calc_op(self.d[r], sm)):\n sm = ST.calc_op(self.d[r], sm)\n r.dec\n return r + 1 - self.size\n sm = ST.calc_op(self.d[r], sm)\n if not ((r and -r) != r): break\n return 0\n {.pop.}\n" var lr = collect(newSeq): for i in 0..<4: for j in i..<4: (i, j) var lri = newSeqWith(4, newSeqWith(4, 0)) for i in 0..= f: rseq[lri[l][r]] = x[1] return (rseq, x[1]) proc composition(f, g: int): int = (if f == INFL: g else: f) proc id(): int = INFL var n = input(int) var a = input(int, n).mapIt(it-1) var lseg = initLazySegTree[(seq[int], int), int](newSeqWith(n, (newSeqWith(lr.len, 0), 1)), op, e, mapping, composition, id) for i in 0..