You are given a permutation p1,p2,…,pnp1,p2,…,pn. A permutation of length nn is a sequence such that each integer between 11 and nn occurs exactly once in the sequence.

Find the number of pairs of indices (l,r)(l,r) (1≤l≤r≤n1≤l≤r≤n) such that the value of the median of pl,pl+1,…,prpl,pl+1,…,pr is exactly the given number mm.

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]a=[4,2,7,5] then its median is 44 since after sorting the sequence, it will look like [2,4,5,7][2,4,5,7] and the left of two middle elements is equal to 44. The median of [7,1,2,9,6][7,1,2,9,6] equals 66 since after sorting, the value 66 will be in the middle of the sequence.

Write a program to find the number of pairs of indices (l,r)(l,r) (1≤l≤r≤n1≤l≤r≤n) such that the value of the median of pl,pl+1,…,prpl,pl+1,…,pr is exactly the given number mm.

The first line contains integers nn and mm (1≤n≤2⋅1051≤n≤2⋅105, 1≤m≤n1≤m≤n) — the length of the given sequence and the required value of the median.

The second line contains a permutation p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n). Each integer between 11 and nn occurs in pp exactly once.

Print the required number.

In the first example, the suitable pairs of indices are: (1,3)(1,3), (2,2)(2,2), (2,3)(2,3) and (2,4)(2,4).

题意：给你n个数和m，问在这n个数中以m为中位数的区间有多少个？

因为要使m为中位数，肯定是m的值位于这些数的中间的部分，即要有比m大的数和比m小的数，且大的数和小的数要相等或者大的数比小的数多一

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

#define debug(a) cout << #a << " " << a << endl

using namespace std;

const int maxn = 2e5 + ;

const int mod = 1e9 + ;

typedef long long ll;

ll a[maxn], vis[maxn];

int main() {

    ll n, m;

    while( cin >> n >> m ) {

        map<ll,ll> mm;

        ll  pos;

        for( ll i = ; i <= n; i ++ ) {

            cin >> a[i];

            if( a[i] == m ) {

                pos = i;

            }

        }

        ll cnt = ;

        for( ll i = pos; i <= n; i ++ ) {

            if( a[i] > m ) {

                cnt ++;

            } else if( a[i] < m ) {

                cnt --;

            }

            mm[cnt] ++;

        }

        ll ans = ;

        cnt = ;

        for( ll i = pos; i >= ; i -- ) {

            if( a[i] > m ) {

                cnt ++;

            } else if( a[i] < m ) {

                cnt --;

            }

            ans += mm[-cnt];

            ans += mm[-cnt];  //个数为偶数，中位数在中间两位的左边一位

        }

        cout << ans << endl;

    }

    return ;

}