#include <bits/stdc++.h>
static void fw_init(int64_t *fw, int sz) { memset(fw, 0, sizeof(fw[0]) * sz); }
static void fw_upd(int64_t *fw, int p, int inc, int sz) {
  for (int i = p; i < sz; i |= i + 1) fw[i] += inc;
}
static int64_t fw_sum(int64_t *fw, int p, int sz) {
  int64_t sum = 0;
  for (int i = p; i >= 0; i = (i & (i + 1)) - 1) sum += fw[i];
  return sum;
}
int64_t cnt(int *aa, int n, int m) {
  int64_t c = 0;
  int s_ofs = n + 1;
  int fw_sz = 2 * n + 2;
  int64_t fw[fw_sz];
  fw_init(fw, fw_sz);
  int ge[n + 1];
  int lt[n + 1];
  ge[0] = lt[0] = 0;
  for (int i = 1; i <= n; i++) {
    lt[i] = lt[i - 1] + (aa[i] < m);
    ge[i] = ge[i - 1] + (aa[i] >= m);
  }
  for (int i = 0; i <= n; i++) {
    int diff = ge[i] - lt[i];
    diff += s_ofs;
    c += fw_sum(fw, diff - 1, fw_sz);
    fw_upd(fw, diff, +1, fw_sz);
  }
  return c;
}
int main(int argc, char **argv) {
  int n, m;
  scanf("%d%d", &n, &m);
  int aa[n + 1];
  for (int i = 1; i <= n; i++) scanf("%d", aa + i);
  printf("%" PRId64 "\n", cnt(aa, n, m) - cnt(aa, n, m + 1));
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
static void fw_init(int64_t *fw, int sz) { memset(fw, 0, sizeof(fw[0]) * sz); }
static void fw_upd(int64_t *fw, int p, int inc, int sz) {
  for (int i = p; i < sz; i |= i + 1) fw[i] += inc;
}
static int64_t fw_sum(int64_t *fw, int p, int sz) {
  int64_t sum = 0;
  for (int i = p; i >= 0; i = (i & (i + 1)) - 1) sum += fw[i];
  return sum;
}
int64_t cnt(int *aa, int n, int m) {
  int64_t c = 0;
  int s_ofs = n + 1;
  int fw_sz = 2 * n + 2;
  int64_t fw[fw_sz];
  fw_init(fw, fw_sz);
  int ge[n + 1];
  int lt[n + 1];
  ge[0] = lt[0] = 0;
  for (int i = 1; i <= n; i++) {
    lt[i] = lt[i - 1] + (aa[i] < m);
    ge[i] = ge[i - 1] + (aa[i] >= m);
  }
  for (int i = 0; i <= n; i++) {
    int diff = ge[i] - lt[i];
    diff += s_ofs;
    c += fw_sum(fw, diff - 1, fw_sz);
    fw_upd(fw, diff, +1, fw_sz);
  }
  return c;
}
int main(int argc, char **argv) {
  int n, m;
  scanf("%d%d", &n, &m);
  int aa[n + 1];
  for (int i = 1; i <= n; i++) scanf("%d", aa + i);
  printf("%" PRId64 "\n", cnt(aa, n, m) - cnt(aa, n, m + 1));
  return 0;
}

```