Algorithm

E1. Median on Segments (Permutations Edition)
time limit per test
3 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1005/problem/E1
input
standard input
output
standard output

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

Find the number of pairs of indices (l,r)(�,�) (1≤l≤r≤n1≤�≤�≤�) such that the value of the median of pl,pl+1,…,pr��,��+1,…,�� 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]�=[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)(�,�) (1≤l≤r≤n1≤�≤�≤�) such that the value of the median of pl,pl+1,…,pr��,��+1,…,�� is exactly the given number m�.

Input

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

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

Output

Print the required number.

Examples
input
Copy
5 4
2 4 5 3 1
output
Copy
4
input
Copy
5 5
1 2 3 4 5
output
Copy
1
input
Copy
15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9
output
Copy
48
Note

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

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, m, idx, sum, a[N], cs[N];
long long res;
map<int, int> fr;

int main() {
  scanf("%d %d", &n, &m);
  idx = -1, sum = 0, res = 0;
  for(int i = 0; i < n; ++i) {
    scanf("%d", a + i);

    if(a[i] == m)
      idx = i;

    if(idx == -1) {
      sum += a[i] > m;
      sum -= a[i] < m;
      ++fr[sum];
    }
  }

  ++fr[0];
  for(int i = idx; i < n; ++i) {
    sum += a[i] > m;
    sum -= a[i] < m;
    res += fr[sum] + fr[sum - 1];
  }

  printf("%lld\n", res);

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5 4
2 4 5 3 1

Output

x
–
+
cmd
4
Advertisements

Demonstration

Codeforces Solution-E1. Median on Segments (Permutations Edition)-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+