import kotlin.math.*
import java.util.*
import java.util.function.IntBinaryOperator
fun main() {
println(solve())
}
val solve: () -> Any = solve@{
val N = readInt()
val A = readIntList()
var ans = 0L
var sum = 0L
for (a in A){
ans += sum * a
sum += a
}
ans
}
//##main
//val mod = 998244353
val mod: Int = 1_000_000_007
fun readString() = readln()
fun readStringList() = readln().split(" ")
fun readInt() = readln().toInt()
fun readLong() = readln().toLong()
fun readIntList() = readln().split(" ").map(String::toInt)
fun readLongList() = readln().split(" ").map(String::toLong)
fun <T> T.alsoPrintln() = also { println(this) }
fun <T, U> T.alsoPrintln(trans: (T) -> U) = also { println(trans(this)) }
fun Boolean.toYesOrNo(yes: String = "Yes", no: String = "No") = if (this) yes else no
fun <E> List<E>.toPair() = this[0] to this[1]
inline fun <reified S, reified T> readPair() =
readln().split(" ").let { it[0].stringTo<S>()!! to it[1].stringTo<T>()!! }
inline fun <reified S, reified T, reified U> readTriple() =
readln().split(" ")
.let { Triple(it[0].stringTo<S>()!!, it[1].stringTo<T>()!!, it[2].stringTo<U>()!!) }
inline fun <reified T> String.stringTo(): T? =
when (T::class) {
String::class -> this as T
Int::class -> toInt() as T
Long::class -> toLong() as T
else -> null
}
fun Int.pow(n: Int) = this.toDouble().pow(n).toInt()
fun minAndMax(a: Int, b: Int) = if (a < b) a to b else b to a
fun <T> T.ifOrThis(bool: (T) -> Boolean, trans: (T) -> T) =
if (bool(this)) trans(this) else this
fun <T> T.ifOrThis(bool: Boolean, trans: (T) -> T) = if (bool) trans(this) else this
val dir4 = listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)
fun <T, R> dfs(now: List<T>, next: List<T>, act: (List<T>) -> R, score: (List<R>) -> R): R {
if (next.isEmpty()) {
return act(now)
}
return score(next.map { dfs(now + it, next - it, act, score) })
}
//acl
/**
* Disjoint set union.
*
* convert from [AtCoderLibraryForJava - DSU](https://github.com/NASU41/AtCoderLibraryForJava/blob/8b3a3b599790a9ca8c7dd92e036af4ddc5be1b05/DSU/DSU.java)
*/
class DSU(private val n: Int) {
private val parentOrSize: IntArray = IntArray(n) { -1 }
/**
* Merge nodes.
*/
fun merge(a: Int, b: Int): Int {
if (a !in 0 until n) throw IndexOutOfBoundsException("a=$a")
if (b !in 0 until n) throw IndexOutOfBoundsException("b=$b")
var x = leader(a)
var y = leader(b)
if (x == y) return x
if (-parentOrSize[x] < -parentOrSize[y]) {
val tmp = x
x = y
y = tmp
}
parentOrSize[x] += parentOrSize[y]
parentOrSize[y] = x
return x
}
/**
* True if two nodes are connected.
*/
fun same(a: Int, b: Int): Boolean {
if (a !in 0 until n) throw IndexOutOfBoundsException("a=$a")
if (b !in 0 until n) throw IndexOutOfBoundsException("b=$b")
return leader(a) == leader(b)
}
/**
* Get its leader node.
*/
fun leader(a: Int): Int {
return if (parentOrSize[a] < 0) {
a
} else {
parentOrSize[a] = leader(parentOrSize[a])
parentOrSize[a]
}
}
/**
* A group's size.
*/
fun size(a: Int): Int {
if (a !in 0 until n) throw IndexOutOfBoundsException("" + a)
return -parentOrSize[leader(a)]
}
/**
* Group by leader.
*/
fun groups(): ArrayList<ArrayList<Int>> {
val leaderBuf = IntArray(n)
val groupSize = IntArray(n)
for (i in 0 until n) {
leaderBuf[i] = leader(i)
groupSize[leaderBuf[i]]++
}
val result = ArrayList<ArrayList<Int>>(n)
for (i in 0 until n) {
result.add(ArrayList(groupSize[i]))
}
for (i in 0 until n) {
result[leaderBuf[i]].add(i)
}
result.removeIf { it.isEmpty() }
return result
}
}
/**
* Fenwick tree(0-indexed).
*
* convert from [AtCoderLibraryForJava - FenwickTree](https://github.com/NASU41/AtCoderLibraryForJava/blob/b0702e6e27f0e2df657df55231a2441c506db5a6/FenwickTree/FenwickTree.java)
*/
class FenwickTree(private val n: Int) {
private val data: LongArray = LongArray(n)
/**
* Fenwick tree constructor.
*/
constructor(data: LongArray) : this(data.size) {
build(data)
}
/**
* Add value x to p.
*/
fun add(p: Int, x: Long) {
var vp = p
assert(vp in 0 until n)
vp++
while (vp <= n) {
data[vp - 1] += x
vp += vp and -vp
}
}
/**
* Calc sum [l, r].
*/
fun sum(l: Int, r: Int): Long {
assert(l in 0..r && r <= n)
return sum(r) - sum(l)
}
private fun sum(r: Int): Long {
var vr = r
var s: Long = 0
while (vr > 0) {
s += data[vr - 1]
vr -= vr and -vr
}
return s
}
private fun build(dat: LongArray) {
System.arraycopy(dat, 0, data, 0, n)
for (i in 1..n) {
val p = i + (i and -i)
if (p <= n) {
data[p - 1] += data[i - 1]
}
}
}
}
/**
* Lazy Segment tree(0-indexed).
*
* convert from [AtCoderLibraryForJava - LazySegTree](https://github.com/NASU41/AtCoderLibraryForJava/blob/e7d9874fb6baac4f566a6af471e80941a55b22b2/LazySegTree/LazySegTree.java)
*/
class LazySegTree<S, F>(
private val MAX: Int,
op: (S, S) -> S,
e: S,
mapping: (F, S) -> S,
composition: (F, F) -> F,
id: F
) {
private val n: Int
private val log: Int
private val op: (S, S) -> S
private val e: S
private val mapping: (F, S) -> S
private val composition: (F, F) -> F
private val id: F
private val dat: Array<S>
private val laz: Array<F>
constructor(
dat: Array<S>,
op: (S, S) -> S,
e: S,
mapping: (F, S) -> S,
composition: (F, F) -> F,
id: F
) : this(dat.size, op, e, mapping, composition, id) {
build(dat)
}
init {
var k = 1
while (k < MAX) k = k shl 1
n = k
log = Integer.numberOfTrailingZeros(n)
this.op = op
this.e = e
this.mapping = mapping
this.composition = composition
this.id = id
@Suppress("UNCHECKED_CAST")
dat = Array(n shl 1) { e as Any } as Array<S>
@Suppress("UNCHECKED_CAST")
laz = Array(n) { id as Any } as Array<F>
Arrays.fill(dat, this.e)
Arrays.fill(laz, this.id)
}
private fun build(dat: Array<S>) {
val l = dat.size
System.arraycopy(dat, 0, this.dat, n, l)
for (i in n - 1 downTo 1) {
this.dat[i] = op(this.dat[i shl 1], this.dat[i shl 1 or 1])
}
}
private fun push(k: Int) {
if (laz[k] === id) return
val lk = k shl 1
val rk = k shl 1 or 1
dat[lk] = mapping(laz[k], dat[lk])
dat[rk] = mapping(laz[k], dat[rk])
if (lk < n) laz[lk] = composition(laz[k], laz[lk])
if (rk < n) laz[rk] = composition(laz[k], laz[rk])
laz[k] = id
}
private fun pushTo(k: Int) {
for (i in log downTo 1) push(k shr i)
}
private fun pushTo(lk: Int, rk: Int) {
for (i in log downTo 1) {
if (lk shr i shl i != lk) push(lk shr i)
if (rk shr i shl i != rk) push(rk shr i)
}
}
private fun updateFrom(k: Int) {
var vk = k
vk = vk shr 1
while (vk > 0) {
dat[vk] = op(dat[vk shl 1], dat[vk shl 1 or 1])
vk = vk shr 1
}
}
private fun updateFrom(lk: Int, rk: Int) {
for (i in 1..log) {
if (lk shr i shl i != lk) {
val lki = lk shr i
dat[lki] = op(dat[lki shl 1], dat[lki shl 1 or 1])
}
if (rk shr i shl i != rk) {
val rki = rk - 1 shr i
dat[rki] = op(dat[rki shl 1], dat[rki shl 1 or 1])
}
}
}
operator fun set(p: Int, x: S) {
var vp = p
exclusiveRangeCheck(vp)
vp += n
pushTo(vp)
dat[vp] = x
updateFrom(vp)
}
operator fun get(p: Int): S {
var vp = p
exclusiveRangeCheck(vp)
vp += n
pushTo(vp)
return dat[vp]
}
fun prod(l: Int, r: Int): S {
var vl = l
var vr = r
require(vl <= vr) { String.format("Invalid range: [%d, %d)", vl, vr) }
inclusiveRangeCheck(vl)
inclusiveRangeCheck(vr)
if (vl == vr) return e
vl += n
vr += n
pushTo(vl, vr)
var sumLeft = e
var sumRight = e
while (vl < vr) {
if (vl and 1 == 1) sumLeft = op(sumLeft, dat[vl++])
if (vr and 1 == 1) sumRight = op(dat[--vr], sumRight)
vl = vl shr 1
vr = vr shr 1
}
return op(sumLeft, sumRight)
}
fun allProd(): S {
return dat[1]
}
fun apply(p: Int, f: F) {
var vp = p
exclusiveRangeCheck(vp)
vp += n
pushTo(vp)
dat[vp] = mapping(f, dat[vp])
updateFrom(vp)
}
fun apply(l: Int, r: Int, f: F) {
var vl = l
var vr = r
require(vl <= vr) { String.format("Invalid range: [%d, %d)", vl, vr) }
inclusiveRangeCheck(vl)
inclusiveRangeCheck(vr)
if (vl == vr) return
vl += n
vr += n
pushTo(vl, vr)
var l2 = vl
var r2 = vr
while (l2 < r2) {
if (l2 and 1 == 1) {
dat[l2] = mapping(f, dat[l2])
if (l2 < n) laz[l2] = composition(f, laz[l2])
l2++
}
if (r2 and 1 == 1) {
r2--
dat[r2] = mapping(f, dat[r2])
if (r2 < n) laz[r2] = composition(f, laz[r2])
}
l2 = l2 shr 1
r2 = r2 shr 1
}
updateFrom(vl, vr)
}
fun maxRight(l: Int, g: (S) -> Boolean): Int {
var vl = l
inclusiveRangeCheck(vl)
require(g(e)) { "Identity element must satisfy the condition." }
if (vl == MAX) return MAX
vl += n
pushTo(vl)
var sum = e
do {
vl = vl shr Integer.numberOfTrailingZeros(vl)
if (!g(op(sum, dat[vl]))) {
while (vl < n) {
push(vl)
vl = vl shl 1
if (g(op(sum, dat[vl]))) {
sum = op(sum, dat[vl])
vl++
}
}
return vl - n
}
sum = op(sum, dat[vl])
vl++
} while (vl and -vl != vl)
return MAX
}
fun minLeft(r: Int, g: (S) -> Boolean): Int {
var vr = r
inclusiveRangeCheck(vr)
require(g(e)) { "Identity element must satisfy the condition." }
if (vr == 0) return 0
vr += n
pushTo(vr - 1)
var sum = e
do {
vr--
while (vr > 1 && vr and 1 == 1) vr = vr shr 1
if (!g(op(dat[vr], sum))) {
while (vr < n) {
push(vr)
vr = vr shl 1 or 1
if (g(op(dat[vr], sum))) {
sum = op(dat[vr], sum)
vr--
}
}
return vr + 1 - n
}
sum = op(dat[vr], sum)
} while (vr and -vr != vr)
return 0
}
private fun exclusiveRangeCheck(p: Int) {
if (p < 0 || p >= MAX) {
throw IndexOutOfBoundsException(
String.format(
"Index %d is not in [%d, %d).",
p,
0,
MAX
)
)
}
}
private fun inclusiveRangeCheck(p: Int) {
if (p < 0 || p > MAX) {
throw IndexOutOfBoundsException(
String.format(
"Index %d is not in [%d, %d].",
p,
0,
MAX
)
)
}
}
// **************** DEBUG **************** //
private var indent = 6
fun setIndent(newIndent: Int) {
indent = newIndent
}
override fun toString(): String {
return toSimpleString()
}
private fun simulatePushAll(): Array<S> {
val simDat = Arrays.copyOf(dat, 2 * n)
val simLaz = Arrays.copyOf(laz, 2 * n)
for (k in 1 until n) {
if (simLaz[k] === id) continue
val lk = k shl 1
val rk = k shl 1 or 1
simDat[lk] = mapping(simLaz[k], simDat[lk])
simDat[rk] = mapping(simLaz[k], simDat[rk])
if (lk < n) simLaz[lk] = composition(simLaz[k], simLaz[lk])
if (rk < n) simLaz[rk] = composition(simLaz[k], simLaz[rk])
simLaz[k] = id
}
return simDat
}
fun toDetailedString(): String {
return toDetailedString(1, 0, simulatePushAll())
}
private fun toDetailedString(k: Int, sp: Int, dat: Array<S>): String {
if (k >= n) return indent(sp) + dat[k]
var s = ""
s += toDetailedString(k shl 1 or 1, sp + indent, dat)
s += "\n"
s += indent(sp) + dat[k]
s += "\n"
s += toDetailedString(k shl 1, sp + indent, dat)
return s
}
fun toSimpleString(): String {
val dat = simulatePushAll()
val sb = StringBuilder()
sb.append('[')
for (i in 0 until n) {
sb.append(dat[i + n])
if (i < n - 1) sb.append(',').append(' ')
}
sb.append(']')
return sb.toString()
}
companion object {
private fun indent(n: Int): String {
var vn = n
val sb = StringBuilder()
while (vn-- > 0) sb.append(' ')
return sb.toString()
}
}
}
/**
* MathLib.
*
* convert from [AtCoderLibraryForJava - MathLib](https://github.com/NASU41/AtCoderLibraryForJava/blob/132179385293fd6c0d522d73f3f48435967fffcb/Math/MathLib.java#L4)
*/
object MathLib {
/**
* xをmで割った余りを返す.
*/
fun safeMod(x: Long, m: Long): Long {
val vx = x % m
return if (vx < 0) vx + m else vx
}
fun invGcd(a: Long, b: Long): LongArray {
var va = a
va = safeMod(va, b)
if (va == 0L) return longArrayOf(b, 0)
var s = b
var t = va
var m0: Long = 0
var m1: Long = 1
while (t > 0) {
val u = s / t
s -= t * u
m0 -= m1 * u
var tmp = s
s = t
t = tmp
tmp = m0
m0 = m1
m1 = tmp
}
if (m0 < 0) m0 += b / s
return longArrayOf(s, m0)
}
/**
* xのn乗をmで割った余りを返す.
*/
fun powMod(x: Long, n: Long, m: Int): Long {
var vx = x
var vn = n
assert(vn >= 0)
assert(m >= 1)
if (m == 1) return 0L
vx = safeMod(vx, m.toLong())
var ans = 1L
while (vn > 0) {
if (vn and 1 == 1L) ans = ans * vx % m
vx = vx * vx % m
vn = vn ushr 1
}
return ans
}
fun crt(r: LongArray, m: LongArray): LongArray {
assert(r.size == m.size)
val n = r.size
var r0: Long = 0
var m0: Long = 1
for (i in 0 until n) {
assert(1 <= m[i])
var r1 = safeMod(r[i], m[i])
var m1 = m[i]
if (m0 < m1) {
var tmp = r0
r0 = r1
r1 = tmp
tmp = m0
m0 = m1
m1 = tmp
}
if (m0 % m1 == 0L) {
if (r0 % m1 != r1) return longArrayOf(0, 0)
continue
}
val ig = invGcd(m0, m1)
val g = ig[0]
val im = ig[1]
val u1 = m1 / g
if ((r1 - r0) % g != 0L) return longArrayOf(0, 0)
val x = (r1 - r0) / g % u1 * im % u1
r0 += x * m0
m0 *= u1
if (r0 < 0) r0 += m0
//System.err.printf("%d %d\n", r0, m0);
}
return longArrayOf(r0, m0)
}
fun floorSum(n: Long, m: Long, a: Long, b: Long): Long {
var va = a
var vb = b
var ans: Long = 0
if (va >= m) {
ans += (n - 1) * n * (va / m) / 2
va %= m
}
if (vb >= m) {
ans += n * (vb / m)
vb %= m
}
val yMax = (va * n + vb) / m
val xMax = yMax * m - vb
if (yMax == 0L) return ans
ans += (n - (xMax + va - 1) / va) * yMax
ans += floorSum(yMax, va, m, (va - xMax % va) % va)
return ans
}
}
/**
* convert from [AtCoderLibraryForJava - MaxFlow](https://github.com/NASU41/AtCoderLibraryForJava/blob/3d5e128641057adbce8b4a727bba4079b8fa2c02/MinCostFlow/MinCostFlow.java)
*/
class MaxFlow(private val n: Int) {
inner class CapEdge internal constructor(
val from: Int,
val to: Int,
var cap: Long,
val rev: Int
)
private var m = 0
private val edges: ArrayList<CapEdge> = ArrayList()
private val count: IntArray = IntArray(n)
private val g: Array<Array<CapEdge?>> = Array(n) { emptyArray<CapEdge?>() }
fun addEdge(from: Int, to: Int, cap: Long): Int {
rangeCheck(from, 0, n)
rangeCheck(to, 0, n)
nonNegativeCheck(cap, "Capacity")
val e = CapEdge(from, to, cap, count[to])
count[from]++
count[to]++
edges.add(e)
return m++
}
fun getEdge(i: Int): CapEdge {
rangeCheck(i, 0, m)
return edges[i]
}
fun changeEdge(i: Int, newCap: Long, newFlow: Long) {
rangeCheck(i, 0, m)
nonNegativeCheck(newCap, "Capacity")
require(newFlow <= newCap) {
String.format(
"Flow %d is greater than capacity %d.",
newCap,
newFlow
)
}
val e = edges[i]
val er = g[e.to][e.rev]
e.cap = newCap - newFlow
er!!.cap = newFlow
}
private fun buildGraph() {
for (i in 0 until n) {
g[i] = arrayOfNulls(count[i])
}
val idx = IntArray(n)
for (e in edges) {
g[e.to][idx[e.to]++] = CapEdge(e.to, e.from, 0, idx[e.from])
g[e.from][idx[e.from]++] = e
}
}
fun maxFlow(s: Int, t: Int): Long {
return flow(s, t, INF)
}
fun flow(s: Int, t: Int, flowLimit: Long): Long {
rangeCheck(s, 0, n)
rangeCheck(t, 0, n)
buildGraph()
var flow: Long = 0
val level = IntArray(n)
val que = IntArray(n)
val iter = IntArray(n)
while (true) {
java.util.Arrays.fill(level, -1)
dinicBFS(s, t, level, que)
if (level[t] < 0) return flow
java.util.Arrays.fill(iter, 0)
while (true) {
val d = dinicDFS(t, s, flowLimit - flow, iter, level)
if (d <= 0) break
flow += d
}
}
}
private fun dinicBFS(s: Int, t: Int, level: IntArray, que: IntArray) {
var hd = 0
var tl = 0
que[tl++] = s
level[s] = 0
while (tl > hd) {
val u = que[hd++]
for (e in g[u]) {
val v = e!!.to
if (e.cap <= 0 || level[v] >= 0) continue
level[v] = level[u] + 1
if (v == t) return
que[tl++] = v
}
}
}
private fun dinicDFS(cur: Int, s: Int, f: Long, iter: IntArray, level: IntArray): Long {
if (cur == s) return f
var res: Long = 0
while (iter[cur] < count[cur]) {
val er = g[cur][iter[cur]++]
val u = er!!.to
val e = g[u][er.rev]
if (level[u] >= level[cur] || e!!.cap <= 0) continue
val d = dinicDFS(u, s, kotlin.math.min(f - res, e.cap), iter, level)
if (d <= 0) continue
e.cap -= d
er.cap += d
res += d
if (res == f) break
}
return res
}
fun fordFulkersonMaxFlow(s: Int, t: Int): Long {
return fordFulkersonFlow(s, t, INF)
}
fun fordFulkersonFlow(s: Int, t: Int, flowLimit: Long): Long {
rangeCheck(s, 0, n)
rangeCheck(t, 0, n)
buildGraph()
val used = BooleanArray(n)
var flow: Long = 0
while (true) {
java.util.Arrays.fill(used, false)
val f = fordFulkersonDFS(s, t, flowLimit - flow, used)
if (f <= 0) return flow
flow += f
}
}
private fun fordFulkersonDFS(cur: Int, t: Int, f: Long, used: BooleanArray): Long {
if (cur == t) return f
used[cur] = true
for (e in g[cur]) {
if (used[e!!.to] || e.cap <= 0) continue
val d = fordFulkersonDFS(e.to, t, kotlin.math.min(f, e.cap), used)
if (d <= 0) continue
e.cap -= d
g[e.to][e.rev]!!.cap += d
return d
}
return 0
}
fun minCut(s: Int): BooleanArray {
rangeCheck(s, 0, n)
val reachable = BooleanArray(n)
val stack = IntArray(n)
var ptr = 0
stack[ptr++] = s
reachable[s] = true
while (ptr > 0) {
val u = stack[--ptr]
for (e in g[u]) {
val v = e!!.to
if (reachable[v] || e.cap <= 0) continue
reachable[v] = true
stack[ptr++] = v
}
}
return reachable
}
private fun rangeCheck(i: Int, minInclusive: Int, maxExclusive: Int) {
if (i < minInclusive || i >= maxExclusive) {
throw IndexOutOfBoundsException(
String.format(
"Index %d out of bounds for length %d",
i,
maxExclusive
)
)
}
}
private fun nonNegativeCheck(cap: Long, attribute: String) {
require(cap >= 0) { String.format("%s %d is negative.", attribute, cap) }
}
companion object {
private const val INF = Long.MAX_VALUE
}
}
/**
* convert from [AtCoderLibraryForJava - MinCostFlow](https://github.com/NASU41/AtCoderLibraryForJava/blob/3d5e128641057adbce8b4a727bba4079b8fa2c02/MinCostFlow/MinCostFlow.java)
*/
class MinCostFlow(private val n: Int) {
inner class WeightedCapEdge internal constructor(
val from: Int,
val to: Int,
var flow: Long,
val cost: Long,
val rev: Int
)
private var m = 0
private val edges: ArrayList<WeightedCapEdge> = ArrayList()
private val count: IntArray = IntArray(n)
private val g: Array<Array<WeightedCapEdge?>> = Array(n) { emptyArray<WeightedCapEdge?>() }
private val potential: LongArray = LongArray(n)
private val dist: LongArray = LongArray(n)
private val prev: Array<WeightedCapEdge?> = arrayOfNulls(n)
fun addEdge(from: Int, to: Int, cap: Long, cost: Long): Int {
rangeCheck(from, 0, n)
rangeCheck(to, 0, n)
nonNegativeCheck(cap, "Capacity")
nonNegativeCheck(cost, "Cost")
val e = WeightedCapEdge(from, to, cap, cost, count[to])
count[from]++
count[to]++
edges.add(e)
return m++
}
private fun buildGraph() {
for (i in 0 until n) {
g[i] = arrayOfNulls(count[i])
}
val idx = IntArray(n)
for (e in edges) {
g[e.to][idx[e.to]++] = WeightedCapEdge(e.to, e.from, 0, -e.cost, idx[e.from])
g[e.from][idx[e.from]++] = e
}
}
private var addFlow: Long = 0
private var addCost: Long = 0
fun minCostMaxFlow(s: Int, t: Int): LongArray {
return minCostFlow(s, t, INF)
}
fun minCostFlow(s: Int, t: Int, flowLimit: Long): LongArray {
rangeCheck(s, 0, n)
rangeCheck(t, 0, n)
require(s != t) { String.format("s = t = %d", s) }
nonNegativeCheck(flowLimit, "Flow")
buildGraph()
var flow: Long = 0
var cost: Long = 0
while (true) {
dijkstra(s, t, flowLimit - flow)
if (addFlow == 0L) break
flow += addFlow
cost += addFlow * addCost
}
return longArrayOf(flow, cost)
}
fun minCostSlope(s: Int, t: Int, flowLimit: Long = INF): ArrayList<LongArray> {
rangeCheck(s, 0, n)
rangeCheck(t, 0, n)
require(s != t) { String.format("s = t = %d", s) }
nonNegativeCheck(flowLimit, "Flow")
buildGraph()
val slope = ArrayList<LongArray>()
var prevCost: Long = -1
var flow: Long = 0
var cost: Long = 0
while (true) {
slope.add(longArrayOf(flow, cost))
dijkstra(s, t, flowLimit - flow)
if (addFlow == 0L) return slope
flow += addFlow
cost += addFlow * addCost
if (addCost == prevCost) {
slope.removeAt(slope.size - 1)
}
prevCost = addCost
}
}
private fun dijkstra(s: Int, t: Int, maxFlow: Long) {
class State(val v: Int, val d: Long) : Comparable<State> {
override operator fun compareTo(other: State): Int {
return if (d == other.d) v - other.v else if (d > other.d) 1 else -1
}
}
java.util.Arrays.fill(dist, INF)
dist[s] = 0
val pq = java.util.PriorityQueue<State>()
pq.add(State(s, 0L))
while (pq.size > 0) {
val st = pq.poll()
val u = st.v
if (st.d != dist[u]) continue
for (e in g[u]) {
if (e!!.flow <= 0) continue
val v = e.to
val nextCost = dist[u] + e.cost + potential[u] - potential[v]
if (nextCost < dist[v]) {
dist[v] = nextCost
prev[v] = e
pq.add(State(v, dist[v]))
}
}
}
if (dist[t] == INF) {
addFlow = 0
addCost = INF
return
}
for (i in 0 until n) {
potential[i] += dist[i]
}
addCost = 0
addFlow = maxFlow
run {
var v = t
while (v != s) {
val e = prev[v]
addCost += e!!.cost
addFlow = kotlin.math.min(addFlow, e.flow)
v = e.from
}
}
var v = t
while (v != s) {
val e = prev[v]
e!!.flow -= addFlow
g[v][e!!.rev]!!.flow += addFlow
v = e!!.from
}
}
fun clearFlow() {
java.util.Arrays.fill(potential, 0)
for (e in edges) {
val flow = e.flow
e.flow += flow
g[e.to][e.rev]!!.flow -= flow
}
}
fun getEdge(i: Int): WeightedCapEdge {
rangeCheck(i, 0, m)
return edges[i]
}
private fun rangeCheck(i: Int, minInclusive: Int, maxExclusive: Int) {
if (i < minInclusive || i >= maxExclusive) {
throw IndexOutOfBoundsException(
String.format(
"Index %d out of bounds for length %d",
i,
maxExclusive
)
)
}
}
private fun nonNegativeCheck(cap: Long, attribute: String) {
require(cap >= 0) { String.format("%s %d is negative.", attribute, cap) }
}
companion object {
private const val INF = Long.MAX_VALUE
}
}
/**
* ModInt を生成するためのファクトリ.
*
* convert from [AtCoderLibraryForJava - FenwickTree](https://github.com/NASU41/AtCoderLibraryForJava/blob/24160d880a5fc6d1caf9b95baa875e47fb568ef3/FenwickTree/FenwickTree.java)
*/
class ModIntFactory(private val mod: Int) {
private val ma = ModArithmetic.of(mod)
/**
* ModInt を生成する.
* 生成された ModInt は、[value] をファクトリ生成時に指定した mod で割った余りを持つ.
*/
fun create(value: Long): ModInt {
val v = (value % mod).let { if (it < 0) it + mod else it }
return if (ma is ModArithmetic.ModArithmeticMontgomery) {
ModInt(ma.generate(v))
} else {
ModInt(v.toInt())
}
}
inner class ModInt(private var rawValue: Int) {
val mod = this@ModIntFactory.mod
val value: Int
get() = if (ma is ModArithmetic.ModArithmeticMontgomery) {
ma.reduce(rawValue.toLong())
} else {
rawValue
}
operator fun plus(mi: ModInt) = ModInt(ma.add(rawValue, mi.rawValue))
operator fun minus(mi: ModInt) = ModInt(ma.sub(rawValue, mi.rawValue))
operator fun times(mi: ModInt) = ModInt(ma.mul(rawValue, mi.rawValue))
operator fun div(mi: ModInt) = ModInt(ma.div(rawValue, mi.rawValue))
/** (this * inv) % mod = 1 を満たすような inv を ModInt として生成して返す. */
fun inv() = ModInt(ma.inv(rawValue))
/** (this ^ [b]) % mod の結果を ModInt として生成して返す. */
fun pow(b: Long) = ModInt(ma.pow(rawValue, b))
/** this を this + [mi] に変更する */
fun addAsg(mi: ModInt): ModInt {
rawValue = ma.add(rawValue, mi.rawValue)
return this
}
/** this を this - [mi] に変更する */
fun subAsg(mi: ModInt): ModInt {
rawValue = ma.sub(rawValue, mi.rawValue)
return this
}
/** this を this * [mi] に変更する */
fun mulAsg(mi: ModInt): ModInt {
rawValue = ma.mul(rawValue, mi.rawValue)
return this
}
/** this を this / [mi] に変更する */
fun divAsg(mi: ModInt): ModInt {
rawValue = ma.div(rawValue, mi.rawValue)
return this
}
override fun toString(): String {
return value.toString()
}
override fun equals(other: Any?): Boolean {
if (other is ModInt) {
return mod == other.mod && value == other.value
}
return false
}
override fun hashCode(): Int {
return (1 * 37 + mod) * 37 + value
}
}
private interface ModArithmetic {
fun mod(): Int
fun add(a: Int, b: Int): Int
fun sub(a: Int, b: Int): Int
fun mul(a: Int, b: Int): Int
fun div(a: Int, b: Int): Int {
return mul(a, inv(b))
}
fun inv(a: Int): Int
fun pow(a: Int, b: Long): Int
class ModArithmetic1 : ModArithmetic {
override fun mod(): Int {
return 1
}
override fun add(a: Int, b: Int): Int {
return 0
}
override fun sub(a: Int, b: Int): Int {
return 0
}
override fun mul(a: Int, b: Int): Int {
return 0
}
override fun inv(a: Int): Int {
throw ArithmeticException("divide by zero")
}
override fun pow(a: Int, b: Long): Int {
return 0
}
}
class ModArithmetic2 : ModArithmetic {
override fun mod(): Int {
return 2
}
override fun add(a: Int, b: Int): Int {
return a xor b
}
override fun sub(a: Int, b: Int): Int {
return a xor b
}
override fun mul(a: Int, b: Int): Int {
return a and b
}
override fun inv(a: Int): Int {
if (a == 0) throw ArithmeticException("divide by zero")
return a
}
override fun pow(a: Int, b: Long): Int {
return if (b == 0L) 1 else a
}
}
class ModArithmetic998244353 : ModArithmetic {
private val mod = 998244353
override fun mod(): Int {
return mod
}
override fun add(a: Int, b: Int): Int {
val res = a + b
return if (res >= mod) res - mod else res
}
override fun sub(a: Int, b: Int): Int {
val res = a - b
return if (res < 0) res + mod else res
}
override fun mul(a: Int, b: Int): Int {
return (a.toLong() * b % mod).toInt()
}
override fun inv(a: Int): Int {
var va = a
var b = mod
var u: Long = 1
var v: Long = 0
while (b >= 1) {
val t = (va / b).toLong()
va -= (t * b).toInt()
val tmp1 = va
va = b
b = tmp1
u -= t * v
val tmp2 = u
u = v
v = tmp2
}
u %= mod.toLong()
if (va != 1) {
throw ArithmeticException("divide by zero")
}
return (if (u < 0) u + mod else u).toInt()
}
override fun pow(a: Int, b: Long): Int {
var vb = b
if (vb < 0) throw ArithmeticException("negative power")
var res: Long = 1
var pow2 = a.toLong()
var idx: Long = 1
while (vb > 0) {
val lsb = vb and -vb
while (lsb != idx) {
pow2 = pow2 * pow2 % mod
idx = idx shl 1
}
res = res * pow2 % mod
vb = vb xor lsb
}
return res.toInt()
}
}
class ModArithmetic1000000007 : ModArithmetic {
private val mod = 1000000007
override fun mod(): Int {
return mod
}
override fun add(a: Int, b: Int): Int {
val res = a + b
return if (res >= mod) res - mod else res
}
override fun sub(a: Int, b: Int): Int {
val res = a - b
return if (res < 0) res + mod else res
}
override fun mul(a: Int, b: Int): Int {
return (a.toLong() * b % mod).toInt()
}
override fun div(a: Int, b: Int): Int {
return mul(a, inv(b))
}
override fun inv(a: Int): Int {
var va = a
var b = mod
var u: Long = 1
var v: Long = 0
while (b >= 1) {
val t = (va / b).toLong()
va -= (t * b).toInt()
val tmp1 = va
va = b
b = tmp1
u -= t * v
val tmp2 = u
u = v
v = tmp2
}
u %= mod.toLong()
if (va != 1) {
throw ArithmeticException("divide by zero")
}
return (if (u < 0) u + mod else u).toInt()
}
override fun pow(a: Int, b: Long): Int {
var vb = b
if (vb < 0) throw ArithmeticException("negative power")
var res: Long = 1
var pow2 = a.toLong()
var idx: Long = 1
while (vb > 0) {
val lsb = vb and -vb
while (lsb != idx) {
pow2 = pow2 * pow2 % mod
idx = idx shl 1
}
res = res * pow2 % mod
vb = vb xor lsb
}
return res.toInt()
}
}
class ModArithmeticMontgomery(mod: Int) : ModArithmeticDynamic(mod) {
private val negInv: Long
private val r2: Long
private val r3: Long
fun generate(x: Long): Int {
return reduce(x * r2)
}
fun reduce(x: Long): Int {
var vx = x
vx = vx + (vx * negInv and 0xffffffffL) * mod ushr 32
return (if (vx < mod) vx else vx - mod).toInt()
}
override fun mul(a: Int, b: Int): Int {
return reduce(a.toLong() * b)
}
override fun inv(a: Int): Int {
var va = a
va = super.inv(va)
return reduce(va * r3)
}
override fun pow(a: Int, b: Long): Int {
return generate(super.pow(a, b).toLong())
}
init {
var inv: Long = 0
var s: Long = 1
var t: Long = 0
for (i in 0..31) {
if (t and 1 == 0L) {
t += mod.toLong()
inv += s
}
t = t shr 1
s = s shl 1
}
val r = (1L shl 32) % mod
negInv = inv
r2 = r * r % mod
r3 = r2 * r % mod
}
}
class ModArithmeticBarrett(mod: Int) : ModArithmeticDynamic(mod) {
private val mh: Long
private val ml: Long
private fun reduce(x: Long): Int {
var vx = x
var z = (vx and mask) * ml
z = (vx and mask) * mh + (vx ushr 32) * ml + (z ushr 32)
z = (vx ushr 32) * mh + (z ushr 32)
vx -= z * mod
return (if (vx < mod) vx else vx - mod).toInt()
}
override fun mul(a: Int, b: Int): Int {
return reduce(a.toLong() * b)
}
companion object {
private const val mask = 0xffffffffL
}
init {
/**
* m = floor(2^64/mod)
* 2^64 = p*mod + q, 2^32 = a*mod + b
* => (a*mod + b)^2 = p*mod + q
* => p = mod*a^2 + 2ab + floor(b^2/mod)
*/
val a = (1L shl 32) / mod
val b = (1L shl 32) % mod
val m = a * a * mod + 2 * a * b + b * b / mod
mh = m ushr 32
ml = m and mask
}
}
open class ModArithmeticDynamic(val mod: Int) : ModArithmetic {
override fun mod(): Int {
return mod
}
override fun add(a: Int, b: Int): Int {
val sum = a + b
return if (sum >= mod) sum - mod else sum
}
override fun sub(a: Int, b: Int): Int {
val sum = a - b
return if (sum < 0) sum + mod else sum
}
override fun mul(a: Int, b: Int): Int {
return (a.toLong() * b % mod).toInt()
}
override fun inv(a: Int): Int {
var va = a
var b = mod
var u: Long = 1
var v: Long = 0
while (b >= 1) {
val t = (va / b).toLong()
va -= (t * b).toInt()
val tmp1 = va
va = b
b = tmp1
u -= t * v
val tmp2 = u
u = v
v = tmp2
}
u %= mod.toLong()
if (va != 1) {
throw ArithmeticException("divide by zero")
}
return (if (u < 0) u + mod else u).toInt()
}
override fun pow(a: Int, b: Long): Int {
var vb = b
if (vb < 0) throw ArithmeticException("negative power")
var res = 1
var pow2 = a
var idx: Long = 1
while (vb > 0) {
val lsb = vb and -vb
while (lsb != idx) {
pow2 = mul(pow2, pow2)
idx = idx shl 1
}
res = mul(res, pow2)
vb = vb xor lsb
}
return res
}
}
companion object {
fun of(mod: Int): ModArithmetic {
return when {
mod <= 0 -> throw IllegalArgumentException()
mod == 1 -> ModArithmetic1()
mod == 2 -> ModArithmetic2()
mod == 998244353 -> ModArithmetic998244353()
mod == 1000000007 -> ModArithmetic1000000007()
mod and 1 == 1 -> ModArithmeticMontgomery(mod)
else -> ModArithmeticBarrett(mod)
}
}
}
}
}
/**
* convert from [AtCoderLibraryForJava - SCC](https://github.com/NASU41/AtCoderLibraryForJava/blob/ee794a298f6d16ab24bd9316e7cae8a9155510e5/SCC/SCC.java)
*/
class SCC(private val n: Int) {
private class Edge(var from: Int, var to: Int)
private var m = 0
private val unorderedEdges: ArrayList<Edge> = ArrayList()
private val start: IntArray = IntArray(n + 1)
private val ids: IntArray = IntArray(n)
private var hasBuilt = false
fun addEdge(from: Int, to: Int) {
rangeCheck(from)
rangeCheck(to)
unorderedEdges.add(Edge(from, to))
start[from + 1]++
m++
}
fun id(i: Int): Int {
if (!hasBuilt) {
throw UnsupportedOperationException(
"Graph hasn't been built."
)
}
rangeCheck(i)
return ids[i]
}
fun build(): Array<IntArray> {
for (i in 1..n) {
start[i] += start[i - 1]
}
val orderedEdges = arrayOfNulls<Edge>(m)
val count = IntArray(n + 1)
System.arraycopy(start, 0, count, 0, n + 1)
for (e in unorderedEdges) {
orderedEdges[count[e.from]++] = e
}
var nowOrd = 0
var groupNum = 0
var k = 0
// parent
val par = IntArray(n)
val vis = IntArray(n)
val low = IntArray(n)
val ord = IntArray(n)
java.util.Arrays.fill(ord, -1)
// u = lower32(stack[i]) : visiting vertex
// j = upper32(stack[i]) : jth child
val stack = LongArray(n)
// size of stack
var ptr = 0
// non-recursional DFS
for (i in 0 until n) {
if (ord[i] >= 0) continue
par[i] = -1
// vertex i, 0th child.
stack[ptr++] = 0L shl 32 or i.toLong()
// stack is not empty
while (ptr > 0) {
// last element
val p = stack[--ptr]
// vertex
val u = (p and 0xffffffffL).toInt()
// jth child
var j = (p ushr 32).toInt()
if (j == 0) { // first visit
ord[u] = nowOrd++
low[u] = ord[u]
vis[k++] = u
}
if (start[u] + j < count[u]) { // there are more children
// jth child
val to = orderedEdges[start[u] + j]!!.to
// incr children counter
stack[ptr++] += 1L shl 32
if (ord[to] == -1) { // new vertex
stack[ptr++] = 0L shl 32 or to.toLong()
par[to] = u
} else { // backward edge
low[u] = kotlin.math.min(low[u], ord[to])
}
} else { // no more children (leaving)
while (j-- > 0) {
val to = orderedEdges[start[u] + j]!!.to
// update lowlink
if (par[to] == u) low[u] = kotlin.math.min(low[u], low[to])
}
if (low[u] == ord[u]) { // root of a component
while (true) { // gathering verticies
val v = vis[--k]
ord[v] = n
ids[v] = groupNum
if (v == u) break
}
groupNum++ // incr the number of components
}
}
}
}
for (i in 0 until n) {
ids[i] = groupNum - 1 - ids[i]
}
val counts = IntArray(groupNum)
for (x in ids) counts[x]++
val groups = Array(groupNum) { intArrayOf() }
for (i in 0 until groupNum) {
groups[i] = IntArray(counts[i])
}
for (i in 0 until n) {
val cmp = ids[i]
groups[cmp][--counts[cmp]] = i
}
hasBuilt = true
return groups
}
private fun rangeCheck(i: Int) {
if (i < 0 || i >= n) {
throw IndexOutOfBoundsException(
String.format(
"Index %d out of bounds for length %d",
i,
n
)
)
}
}
}
/**
* Segment tree(0-indexed)
*
* convert from [AtCoderLibraryForJava - SegTree](https://github.com/NASU41/AtCoderLibraryForJava/blob/24160d880a5fc6d1caf9b95baa875e47fb568ef3/SegTree/SegTree.java)
*/
class SegTree<S>(n: Int, op: (S, S) -> S, e: S) {
private val max: Int = n
private val n: Int
private val op: (S, S) -> S
private val e: S
private val data: Array<S>
init {
var k = 1
while (k < n) k = k shl 1
this.n = k
this.e = e
this.op = op
@Suppress("UNCHECKED_CAST")
data = Array(this.n shl 1) { this.e as Any } as Array<S>
java.util.Arrays.fill(data, this.e)
}
constructor(dat: Array<S>, op: (S, S) -> S, e: S) : this(dat.size, op, e) {
build(dat)
}
private fun build(dat: Array<S>) {
val l = dat.size
System.arraycopy(dat, 0, data, n, l)
for (i in n - 1 downTo 1) {
data[i] = op(data[i shl 1 or 0], data[i shl 1 or 1])
}
}
operator fun set(p: Int, x: S) {
var vp = p
exclusiveRangeCheck(vp)
data[n.let { vp += it; vp }] = x
vp = vp shr 1
while (vp > 0) {
data[vp] = op(data[vp shl 1 or 0], data[vp shl 1 or 1])
vp = vp shr 1
}
}
operator fun get(p: Int): S {
exclusiveRangeCheck(p)
return data[p + n]
}
fun prod(l: Int, r: Int): S {
var vl = l
var vr = r
require(vl <= vr) { String.format("Invalid range: [%d, %d)", vl, vr) }
inclusiveRangeCheck(vl)
inclusiveRangeCheck(vr)
var sumLeft = e
var sumRight = e
vl += n
vr += n
while (vl < vr) {
if (vl and 1 == 1) sumLeft = op(sumLeft, data[vl++])
if (vr and 1 == 1) sumRight = op(data[--vr], sumRight)
vl = vl shr 1
vr = vr shr 1
}
return op(sumLeft, sumRight)
}
fun allProd(): S {
return data[1]
}
fun maxRight(l: Int, f: (S) -> Boolean): Int {
var vl = l
inclusiveRangeCheck(vl)
require(f(e)) { "Identity element must satisfy the condition." }
if (vl == max) return max
vl += n
var sum = e
do {
vl = vl shr Integer.numberOfTrailingZeros(vl)
if (!f(op(sum, data[vl]))) {
while (vl < n) {
vl = vl shl 1
if (f(op(sum, data[vl]))) {
sum = op(sum, data[vl])
vl++
}
}
return vl - n
}
sum = op(sum, data[vl])
vl++
} while (vl and -vl != vl)
return max
}
fun minLeft(r: Int, f: (S) -> Boolean): Int {
var vr = r
inclusiveRangeCheck(vr)
require(f(e)) { "Identity element must satisfy the condition." }
if (vr == 0) return 0
vr += n
var sum = e
do {
vr--
while (vr > 1 && vr and 1 == 1) vr = vr shr 1
if (!f(op(data[vr], sum))) {
while (vr < n) {
vr = vr shl 1 or 1
if (f(op(data[vr], sum))) {
sum = op(data[vr], sum)
vr--
}
}
return vr + 1 - n
}
sum = op(data[vr], sum)
} while (vr and -vr != vr)
return 0
}
private fun exclusiveRangeCheck(p: Int) {
if (p < 0 || p >= max) {
throw IndexOutOfBoundsException(
String.format(
"Index %d out of bounds for the range [%d, %d).",
p,
0,
max
)
)
}
}
private fun inclusiveRangeCheck(p: Int) {
if (p < 0 || p > max) {
throw IndexOutOfBoundsException(
String.format(
"Index %d out of bounds for the range [%d, %d].",
p,
0,
max
)
)
}
}
// **************** DEBUG **************** //
private var indent = 6
fun setIndent(newIndent: Int) {
indent = newIndent
}
override fun toString(): String {
return toSimpleString()
}
fun toDetailedString(): String {
return toDetailedString(1, 0)
}
private fun toDetailedString(k: Int, sp: Int): String {
if (k >= n) return indent(sp) + data[k]
var s = ""
s += toDetailedString(k shl 1 or 1, sp + indent)
s += "\n"
s += indent(sp) + data[k]
s += "\n"
s += toDetailedString(k shl 1 or 0, sp + indent)
return s
}
fun toSimpleString(): String {
val sb = StringBuilder()
sb.append('[')
for (i in 0 until n) {
sb.append(data[i + n])
if (i < n - 1) sb.append(',').append(' ')
}
sb.append(']')
return sb.toString()
}
companion object {
private fun indent(n: Int): String {
var vn = n
val sb = StringBuilder()
while (vn-- > 0) sb.append(' ')
return sb.toString()
}
}
}
/**
* StringAlgorithm
*
* convert from [AtCoderLibraryForJava - StringAlgorithm](https://github.com/NASU41/AtCoderLibraryForJava/blob/df25ae43276dff808c3fff91baa6dab5be372c00/StringAlgorithm/StringAlgorithm.java)
*/
object StringAlgorithm {
private fun saNaive(s: IntArray): IntArray {
val n = s.size
val sa = IntArray(n)
for (i in 0 until n) {
sa[i] = i
}
insertionsortUsingComparator(sa, IntBinaryOperator { l: Int, r: Int ->
var vl = l
var vr = r
while (vl < n && vr < n) {
if (s[vl] != s[vr]) return@IntBinaryOperator s[vl] - s[vr]
vl++
vr++
}
-(vl - vr)
})
return sa
}
private fun saDoubling(s: IntArray): IntArray {
val n = s.size
val sa = IntArray(n)
for (i in 0 until n) {
sa[i] = i
}
var rnk = s.copyOf(n)
var tmp = IntArray(n)
var k = 1
while (k < n) {
val vk = k
val vrnk = rnk
val cmp = java.util.function.IntBinaryOperator { x: Int, y: Int ->
if (vrnk[x] != vrnk[y]) return@IntBinaryOperator vrnk[x] - vrnk[y]
val rx = if (x + vk < n) vrnk[x + vk] else -1
val ry = if (y + vk < n) vrnk[y + vk] else -1
rx - ry
}
mergesortUsingComparator(sa, cmp)
tmp[sa[0]] = 0
for (i in 1 until n) {
tmp[sa[i]] = tmp[sa[i - 1]] + if (cmp.applyAsInt(sa[i - 1], sa[i]) < 0) 1 else 0
}
val buf = tmp
tmp = rnk
rnk = buf
k *= 2
}
return sa
}
private fun insertionsortUsingComparator(
a: IntArray,
comparator: java.util.function.IntBinaryOperator
) {
val n = a.size
for (i in 1 until n) {
val tmp = a[i]
if (comparator.applyAsInt(a[i - 1], tmp) > 0) {
var j = i
do {
a[j] = a[j - 1]
j--
} while (j > 0 && comparator.applyAsInt(a[j - 1], tmp) > 0)
a[j] = tmp
}
}
}
private fun mergesortUsingComparator(
a: IntArray,
comparator: java.util.function.IntBinaryOperator
) {
val n = a.size
val work = IntArray(n)
var block = 1
while (block <= n) {
val block2 = block shl 1
var l = 0
val max = n - block
while (l < max) {
val m = l + block
val r = kotlin.math.min(l + block2, n)
System.arraycopy(a, l, work, 0, block)
var i = l
var wi = 0
var ti = m
while (true) {
if (ti == r) {
System.arraycopy(work, wi, a, i, block - wi)
break
}
if (comparator.applyAsInt(work[wi], a[ti]) > 0) {
a[i] = a[ti++]
} else {
a[i] = work[wi++]
if (wi == block) break
}
i++
}
l += block2
}
block = block shl 1
}
}
private const val THRESHOLD_NAIVE = 50
private const val THRESHOLD_DOUBLING = 0
private fun sais(s: IntArray, upper: Int): IntArray {
val n = s.size
if (n == 0) return IntArray(0)
if (n == 1) return intArrayOf(0)
if (n == 2) {
return if (s[0] < s[1]) {
intArrayOf(0, 1)
} else {
intArrayOf(1, 0)
}
}
if (n < THRESHOLD_NAIVE) {
return saNaive(s)
}
// if (n < THRESHOLD_DOUBLING) {
// return saDoubling(s);
// }
val sa = IntArray(n)
val ls = BooleanArray(n)
for (i in n - 2 downTo 0) {
ls[i] = if (s[i] == s[i + 1]) ls[i + 1] else s[i] < s[i + 1]
}
val sumL = IntArray(upper + 1)
val sumS = IntArray(upper + 1)
for (i in 0 until n) {
if (ls[i]) {
sumL[s[i] + 1]++
} else {
sumS[s[i]]++
}
}
for (i in 0..upper) {
sumS[i] += sumL[i]
if (i < upper) sumL[i + 1] += sumS[i]
}
val induce = java.util.function.Consumer { lms: IntArray ->
java.util.Arrays.fill(sa, -1)
val buf = IntArray(upper + 1)
System.arraycopy(sumS, 0, buf, 0, upper + 1)
for (d in lms) {
if (d == n) continue
sa[buf[s[d]]++] = d
}
System.arraycopy(sumL, 0, buf, 0, upper + 1)
sa[buf[s[n - 1]]++] = n - 1
for (i in 0 until n) {
val v = sa[i]
if (v >= 1 && !ls[v - 1]) {
sa[buf[s[v - 1]]++] = v - 1
}
}
System.arraycopy(sumL, 0, buf, 0, upper + 1)
for (i in n - 1 downTo 0) {
val v = sa[i]
if (v >= 1 && ls[v - 1]) {
sa[--buf[s[v - 1] + 1]] = v - 1
}
}
}
val lmsMap = IntArray(n + 1)
java.util.Arrays.fill(lmsMap, -1)
var m = 0
for (i in 1 until n) {
if (!ls[i - 1] && ls[i]) {
lmsMap[i] = m++
}
}
val lms = IntArray(m)
run {
var p = 0
for (i in 1 until n) {
if (!ls[i - 1] && ls[i]) {
lms[p++] = i
}
}
}
induce.accept(lms)
if (m > 0) {
val sortedLms = IntArray(m)
run {
var p = 0
for (v in sa) {
if (lmsMap[v] != -1) {
sortedLms[p++] = v
}
}
}
val recS = IntArray(m)
var recUpper = 0
recS[lmsMap[sortedLms[0]]] = 0
for (i in 1 until m) {
var l = sortedLms[i - 1]
var r = sortedLms[i]
val endL = if (lmsMap[l] + 1 < m) lms[lmsMap[l] + 1] else n
val endR = if (lmsMap[r] + 1 < m) lms[lmsMap[r] + 1] else n
var same = true
if (endL - l != endR - r) {
same = false
} else {
while (l < endL && s[l] == s[r]) {
l++
r++
}
if (l == n || s[l] != s[r]) same = false
}
if (!same) {
recUpper++
}
recS[lmsMap[sortedLms[i]]] = recUpper
}
val recSA = sais(recS, recUpper)
for (i in 0 until m) {
sortedLms[i] = lms[recSA[i]]
}
induce.accept(sortedLms)
}
return sa
}
fun suffixArray(s: IntArray, upper: Int): IntArray {
assert(0 <= upper)
for (d in s) {
assert(d in 0..upper)
}
return sais(s, upper)
}
fun suffixArray(s: IntArray): IntArray {
val n = s.size
val vals = s.copyOf(n)
java.util.Arrays.sort(vals)
var p = 1
for (i in 1 until n) {
if (vals[i] != vals[i - 1]) {
vals[p++] = vals[i]
}
}
val s2 = IntArray(n)
for (i in 0 until n) {
s2[i] = java.util.Arrays.binarySearch(vals, 0, p, s[i])
}
return sais(s2, p)
}
fun suffixArray(s: CharArray): IntArray {
val n = s.size
val s2 = IntArray(n)
for (i in 0 until n) {
s2[i] = s[i].toInt()
}
return sais(s2, 255)
}
fun suffixArray(s: String): IntArray {
return suffixArray(s.toCharArray())
}
fun lcpArray(s: IntArray, sa: IntArray): IntArray {
val n = s.size
assert(n >= 1)
val rnk = IntArray(n)
for (i in 0 until n) {
rnk[sa[i]] = i
}
val lcp = IntArray(n - 1)
var h = 0
for (i in 0 until n) {
if (h > 0) h--
if (rnk[i] == 0) {
continue
}
val j = sa[rnk[i] - 1]
while (j + h < n && i + h < n) {
if (s[j + h] != s[i + h]) break
h++
}
lcp[rnk[i] - 1] = h
}
return lcp
}
fun lcpArray(s: CharArray, sa: IntArray): IntArray {
val n = s.size
val s2 = IntArray(n)
for (i in 0 until n) {
s2[i] = s[i].code
}
return lcpArray(s2, sa)
}
fun lcpArray(s: String, sa: IntArray): IntArray {
return lcpArray(s.toCharArray(), sa)
}
fun zAlgorithm(s: IntArray): IntArray {
val n = s.size
if (n == 0) return IntArray(0)
val z = IntArray(n)
var i = 1
var j = 0
while (i < n) {
var k = if (j + z[j] <= i) 0 else kotlin.math.min(j + z[j] - i, z[i - j])
while (i + k < n && s[k] == s[i + k]) k++
z[i] = k
if (j + z[j] < i + z[i]) j = i
i++
}
z[0] = n
return z
}
fun zAlgorithm(s: CharArray): IntArray {
val n = s.size
if (n == 0) return IntArray(0)
val z = IntArray(n)
var i = 1
var j = 0
while (i < n) {
var k = if (j + z[j] <= i) 0 else kotlin.math.min(j + z[j] - i, z[i - j])
while (i + k < n && s[k] == s[i + k]) k++
z[i] = k
if (j + z[j] < i + z[i]) j = i
i++
}
z[0] = n
return z
}
fun zAlgorithm(s: String): IntArray {
return zAlgorithm(s.toCharArray())
}
}
/**
* convert from [AtCoderLibraryForJava - TwoSAT](https://github.com/NASU41/AtCoderLibraryForJava/blob/e2dcebabdbd41d5c87dc73cb46416864a3ea3f6c/2SAT/TwoSAT.java)
*/
class TwoSAT(private val n: Int) {
private val scc: InternalSCC = InternalSCC(2 * n)
private val answer: BooleanArray = BooleanArray(n)
private var hasCalledSatisfiable = false
private var existsAnswer = false
fun addClause(x: Int, f: Boolean, y: Int, g: Boolean) {
rangeCheck(x)
rangeCheck(y)
scc.addEdge(x shl 1 or if (f) 0 else 1, y shl 1 or if (g) 1 else 0)
scc.addEdge(y shl 1 or if (g) 0 else 1, x shl 1 or if (f) 1 else 0)
}
fun addImplication(x: Int, f: Boolean, y: Int, g: Boolean) {
addClause(x, !f, y, g)
}
fun addNand(x: Int, f: Boolean, y: Int, g: Boolean) {
addClause(x, !f, y, !g)
}
fun satisfiable(): Boolean {
hasCalledSatisfiable = true
val ids = scc.ids()
for (i in 0 until n) {
if (ids[i shl 1 or 0] == ids[i shl 1 or 1]) return false.also { existsAnswer = it }
answer[i] = ids[i shl 1 or 0] < ids[i shl 1 or 1]
}
return true.also { existsAnswer = it }
}
fun answer(): BooleanArray? {
if (!hasCalledSatisfiable) {
throw UnsupportedOperationException(
"Call TwoSAT#satisfiable at least once before TwoSAT#answer."
)
}
return if (existsAnswer) answer else null
}
private fun rangeCheck(x: Int) {
if (x < 0 || x >= n) {
throw IndexOutOfBoundsException(
String.format(
"Index %d out of bounds for length %d",
x,
n
)
)
}
}
private class EdgeList(cap: Int) {
var a: LongArray
var ptr = 0
fun add(upper: Int, lower: Int) {
if (ptr == a.size) grow()
a[ptr++] = upper.toLong() shl 32 or lower.toLong()
}
fun grow() {
val b = LongArray(a.size shl 1)
System.arraycopy(a, 0, b, 0, a.size)
a = b
}
init {
a = LongArray(cap)
}
}
private class InternalSCC(val n: Int) {
var m = 0
val unorderedEdges: EdgeList = EdgeList(n)
val start: IntArray = IntArray(n + 1)
fun addEdge(from: Int, to: Int) {
unorderedEdges.add(from, to)
start[from + 1]++
m++
}
fun ids(): IntArray {
for (i in 1..n) {
start[i] += start[i - 1]
}
val orderedEdges = IntArray(m)
val count = IntArray(n + 1)
System.arraycopy(start, 0, count, 0, n + 1)
for (i in 0 until m) {
val e = unorderedEdges.a[i]
orderedEdges[count[(e ushr 32).toInt()]++] = (e and mask).toInt()
}
var nowOrd = 0
var groupNum = 0
var k = 0
val par = IntArray(n)
val vis = IntArray(n)
val low = IntArray(n)
val ord = IntArray(n)
java.util.Arrays.fill(ord, -1)
val ids = IntArray(n)
val stack = LongArray(n)
var ptr = 0
for (i in 0 until n) {
if (ord[i] >= 0) continue
par[i] = -1
stack[ptr++] = i.toLong()
while (ptr > 0) {
val p = stack[--ptr]
val u = (p and mask).toInt()
var j = (p ushr 32).toInt()
if (j == 0) {
ord[u] = nowOrd++
low[u] = ord[u]
vis[k++] = u
}
if (start[u] + j < count[u]) {
val to = orderedEdges[start[u] + j]
stack[ptr++] += 1L shl 32
if (ord[to] == -1) {
stack[ptr++] = to.toLong()
par[to] = u
} else {
low[u] = kotlin.math.min(low[u], ord[to])
}
} else {
while (j-- > 0) {
val to = orderedEdges[start[u] + j]
if (par[to] == u) low[u] = kotlin.math.min(low[u], low[to])
}
if (low[u] == ord[u]) {
while (true) {
val v = vis[--k]
ord[v] = n
ids[v] = groupNum
if (v == u) break
}
groupNum++
}
}
}
}
for (i in 0 until n) {
ids[i] = groupNum - 1 - ids[i]
}
return ids
}
companion object {
const val mask = 0xffffffffL
}
}
}
Main.kt:11:9: warning: variable 'N' is never used
val N = readInt()
^
Main.kt:2044:26: warning: 'toInt(): Int' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
s2[i] = s[i].toInt()
^