You are given a permutation $p_1, p_2, \dots, p_n$. A permutation of length $n$ is a sequence such that each integer between $1$ and $n$ occurs exactly once in the sequence.
Find the number of pairs of indices $(l, r)$ ($1 \le l \le r \le n$) such that the value of the median of $p_l, p_{l+1}, \dots, p_r$ is exactly the given number $m$.
The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used.
For example, if $a=[4, 2, 7, 5]$ then its median is $4$ since after sorting the sequence, it will look like $[2, 4, 5, 7]$ and the left of two middle elements is equal to $4$. The median of $[7, 1, 2, 9, 6]$ equals $6$ since after sorting, the value $6$ will be in the middle of the sequence.
Write a program to find the number of pairs of indices $(l, r)$ ($1 \le l \le r \le n$) such that the value of the median of $p_l, p_{l+1}, \dots, p_r$ is exactly the given number $m$.Input
The first line contains integers $n$ and $m$ ($1 \le n \le 2\cdot10^5$, $1 \le m \le n$) — the length of the given sequence and the required value of the median.
The second line contains a permutation $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Each integer between $1$ and $n$ occurs in $p$ exactly once.Output
Print the required number.Examplesinput
5 4
2 4 5 3 1
output
4
input
5 5
1 2 3 4 5
output
1
input
15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9
output
48
Note
In the first example, the suitable pairs of indices are: $(1, 3)$, $(2, 2)$, $(2, 3)$ and $(2, 4)$.
Solution:
private fun readLn() = readLine()!! // string line private fun readInt() = readLn().toInt() // single int private fun readLong() = readLn().toLong() // single long private fun readDouble() = readLn().toDouble() // single double private fun readStrings() = readLn().split(" ") // list of strings private fun readInts() = readStrings().map { it.toInt() } // list of ints private fun readLongs() = readStrings().map { it.toLong() } // list of longs private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles var fenw = IntArray(0) fun modify(q: Int, v: Int) { var x = q while (x < fenw.size) { fenw[x] += v x = (x or (x + 1)) } } fun get(q: Int) : Int { var x = q var res = 0 while (x >= 0) { res += fenw[x] x = (x and (x + 1)) - 1 } return res } fun count(a: IntArray) : Long { var n = a.size fenw = IntArray(2 * n + 1) {0} var s = n modify(s, 1) var ans: Long = 0L a.forEach { s += it ans += get(s - 1) modify(s, 1) } return ans } fun main(args: Array<String>) { var (n, m) = readInts() var a = readInts() var b = IntArray(n) {it -> if (a[it] > m) 1 else -1} var c = IntArray(n) {it -> if (a[it] >= m) 1 else -1} println(count(c) - count(b)) }