#include <bits/stdc++.h>
using namespace std::chrono;
using namespace std;
bool IOerror = 0;
inline char nc() {
  static char buf[1000000], *p1 = buf + 1000000, *pend = buf + 1000000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 1000000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline int getint() {
  int x = 0;
  char ch;
  int sgn = 1;
  while (blank(ch = nc()))
    ;
  if (IOerror) return 0;
  if (ch == '-') sgn = -1, ch = nc();
  for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
    ;
  return x * sgn;
}
inline long long getll() {
  long long x;
  scanf("%lld", &x);
  return x;
}
inline double getdb() {
  static double x;
  scanf("%lf", &x);
  return x;
}
template <typename T>
void updmax(T& a, T const& b) {
  a = max(a, b);
}
template <typename T>
void updmin(T& a, T const& b) {
  a = min(a, b);
}
template <typename T>
int Descr(T* from, T* to) {
  sort(from, to);
  return (int)(unique(from, to) - from);
}
template <typename T>
int LBound(T* from, T* to, T const& val) {
  return (int)(lower_bound(from, to, val) - from);
}
template <typename T>
int UBound(T* from, T* to, T const& val) {
  return (int)(upper_bound(from, to, val) - from);
}
time_point<system_clock> timing;
void TimingBegin() { timing = system_clock::now(); }
void TimingEnd(const char* c = "time:") {
  auto end = system_clock::now();
  auto d = duration_cast<microseconds>(end - timing);
  printf("%s %.10f\n", c,
         double(d.count()) * microseconds::period::num /
             microseconds::period::den);
}
void TimingTick(const char* c = "time:") {
  TimingEnd(c);
  TimingBegin();
}
void bout(int x) {
  while (x) printf("%d", x & 1), x >>= 1;
}
const int mxn = 2e5 + 50;
int v[mxn];
struct px {
  int a, b;
};
bool operator<(px const& A, px const& B) {
  return A.a == B.a ? A.b > B.b : A.a > B.a;
}
px d[mxn];
int n, k;
int s[mxn * 2];
void inc(int p, int x) {
  while (p <= mxn * 2 - 1) {
    s[p] += x;
    p += p & -p;
  }
}
int getsum(int p) {
  int res = 0;
  while (p) {
    res += s[p];
    p -= p & -p;
  }
  return res;
}
unsigned long long Solve(int const& l, int const& r) {
  if (l == r) return v[l] == k;
  unsigned long long res = 0;
  const int mid = (l + r) / 2;
  for (int i = l, lim__lim = (r); i <= lim__lim; i++) {
    d[i].a = v[i] < k;
    d[i].b = v[i] > k;
  }
  for (int i = mid - 1, lim__lim = (l); i >= lim__lim; i--) {
    d[i].a += d[i + 1].a;
    d[i].b += d[i + 1].b;
  }
  for (int i = mid + 2, lim__lim = (r); i <= lim__lim; i++) {
    d[i].a += d[i - 1].a;
    d[i].b += d[i - 1].b;
  }
  for (int i = l, lim__lim = (mid); i <= lim__lim; i++) {
    d[i].a = 2 * d[i].a + i;
    d[i].b = 2 * d[i].b + i;
  }
  for (int i = mid + 1, lim__lim = (r); i <= lim__lim; i++) {
    d[i].a = i - 2 * d[i].a;
    d[i].b = i - 2 * d[i].b + 1;
  }
  sort(d + l, d + mid + 1);
  sort(d + mid + 1, d + r + 1);
  for (int i = l, lim__lim = (r); i <= lim__lim; i++) {
    d[i].a += mxn;
    d[i].b += mxn;
  }
  int j = mid + 1;
  for (int i = l, lim__lim = (mid); i <= lim__lim; i++) {
    while (j <= r && d[j].a >= d[i].a) {
      inc(d[j++].b, 1);
    }
    res += j - mid - 1 - getsum(d[i].b - 1);
  }
  while (j != mid + 1) inc(d[--j].b, -1);
  assert(j == mid + 1);
  return res + Solve(l, mid) + Solve(mid + 1, r);
}
int main() {
  n = getint();
  k = getint();
  for (int i = 0, lim__lim = (n - 1); i <= lim__lim; i++) v[i] = getint();
  unsigned long long ans = Solve(0, n - 1);
  printf("%llu\n", ans);
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

You are given a permutation p_1, p_2, ..., 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 ≤ l ≤ r ≤ n) such that the value of the median of p_l, p_{l+1}, ..., 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 ≤ l ≤ r ≤ n) such that the value of the median of p_l, p_{l+1}, ..., p_r is exactly the given number m.

Input

The first line contains integers n and m (1 ≤ n ≤ 2⋅10^5, 1 ≤ m ≤ n) — the length of the given sequence and the required value of the median.

The second line contains a permutation p_1, p_2, ..., p_n (1 ≤ p_i ≤ n). Each integer between 1 and n occurs in p exactly once.

Output

Print the required number.

Examples

Input

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).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std::chrono;
using namespace std;
bool IOerror = 0;
inline char nc() {
  static char buf[1000000], *p1 = buf + 1000000, *pend = buf + 1000000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 1000000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline int getint() {
  int x = 0;
  char ch;
  int sgn = 1;
  while (blank(ch = nc()))
    ;
  if (IOerror) return 0;
  if (ch == '-') sgn = -1, ch = nc();
  for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
    ;
  return x * sgn;
}
inline long long getll() {
  long long x;
  scanf("%lld", &x);
  return x;
}
inline double getdb() {
  static double x;
  scanf("%lf", &x);
  return x;
}
template <typename T>
void updmax(T& a, T const& b) {
  a = max(a, b);
}
template <typename T>
void updmin(T& a, T const& b) {
  a = min(a, b);
}
template <typename T>
int Descr(T* from, T* to) {
  sort(from, to);
  return (int)(unique(from, to) - from);
}
template <typename T>
int LBound(T* from, T* to, T const& val) {
  return (int)(lower_bound(from, to, val) - from);
}
template <typename T>
int UBound(T* from, T* to, T const& val) {
  return (int)(upper_bound(from, to, val) - from);
}
time_point<system_clock> timing;
void TimingBegin() { timing = system_clock::now(); }
void TimingEnd(const char* c = "time:") {
  auto end = system_clock::now();
  auto d = duration_cast<microseconds>(end - timing);
  printf("%s %.10f\n", c,
         double(d.count()) * microseconds::period::num /
             microseconds::period::den);
}
void TimingTick(const char* c = "time:") {
  TimingEnd(c);
  TimingBegin();
}
void bout(int x) {
  while (x) printf("%d", x & 1), x >>= 1;
}
const int mxn = 2e5 + 50;
int v[mxn];
struct px {
  int a, b;
};
bool operator<(px const& A, px const& B) {
  return A.a == B.a ? A.b > B.b : A.a > B.a;
}
px d[mxn];
int n, k;
int s[mxn * 2];
void inc(int p, int x) {
  while (p <= mxn * 2 - 1) {
    s[p] += x;
    p += p & -p;
  }
}
int getsum(int p) {
  int res = 0;
  while (p) {
    res += s[p];
    p -= p & -p;
  }
  return res;
}
unsigned long long Solve(int const& l, int const& r) {
  if (l == r) return v[l] == k;
  unsigned long long res = 0;
  const int mid = (l + r) / 2;
  for (int i = l, lim__lim = (r); i <= lim__lim; i++) {
    d[i].a = v[i] < k;
    d[i].b = v[i] > k;
  }
  for (int i = mid - 1, lim__lim = (l); i >= lim__lim; i--) {
    d[i].a += d[i + 1].a;
    d[i].b += d[i + 1].b;
  }
  for (int i = mid + 2, lim__lim = (r); i <= lim__lim; i++) {
    d[i].a += d[i - 1].a;
    d[i].b += d[i - 1].b;
  }
  for (int i = l, lim__lim = (mid); i <= lim__lim; i++) {
    d[i].a = 2 * d[i].a + i;
    d[i].b = 2 * d[i].b + i;
  }
  for (int i = mid + 1, lim__lim = (r); i <= lim__lim; i++) {
    d[i].a = i - 2 * d[i].a;
    d[i].b = i - 2 * d[i].b + 1;
  }
  sort(d + l, d + mid + 1);
  sort(d + mid + 1, d + r + 1);
  for (int i = l, lim__lim = (r); i <= lim__lim; i++) {
    d[i].a += mxn;
    d[i].b += mxn;
  }
  int j = mid + 1;
  for (int i = l, lim__lim = (mid); i <= lim__lim; i++) {
    while (j <= r && d[j].a >= d[i].a) {
      inc(d[j++].b, 1);
    }
    res += j - mid - 1 - getsum(d[i].b - 1);
  }
  while (j != mid + 1) inc(d[--j].b, -1);
  assert(j == mid + 1);
  return res + Solve(l, mid) + Solve(mid + 1, r);
}
int main() {
  n = getint();
  k = getint();
  for (int i = 0, lim__lim = (n - 1); i <= lim__lim; i++) v[i] = getint();
  unsigned long long ans = Solve(0, n - 1);
  printf("%llu\n", ans);
  return 0;
}

```