시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 216 97 79 54.483%

문제

1부터 N까지 자연수 N개로 이루어진 수열 A가 있다. 각 자연수는 수열에서 한 번씩만 등장한다.

A의 부분 수열은 A의 앞과 뒤에서 숫자를 제거해서 만들 수 있다.

길이가 홀수이면서 중앙값이 B인 A의 부분 수열의 개수를 구하는 프로그램을 작성하시오. 중앙값이란 크기 순으로 수열을 정렬했을 때, 가운데에 있는 숫자이다. 예를 들어, {5, 1, 3}의 중앙값은 3이다.

입력

첫째 줄에 N과 B가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ B ≤ N)

둘째 줄에는 수열 A의 원소가 공백으로 구분되어서 주어진다.

출력

첫째 줄에 중앙값이 B인 A의 부분 수열의 개수를 출력한다.

예제 입력 1

7 4
5 7 2 4 3 1 6

예제 출력 1

4

힌트

{4}, {7, 2, 4}, {5, 7, 2, 4, 3}, {5, 7, 2, 4, 3, 1, 6}

W3sicHJvYmxlbV9pZCI6IjMwMTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzkxMVx1YzU1OVx1YWMxMiIsImRlc2NyaXB0aW9uIjoiXHJcbjxwPlxyXG5cdDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0IEFcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjNzkwXHVjNWYwXHVjMjE4XHViMjk0IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWQ1NWMgXHViYzg4XHVjNTI5XHViOWNjIFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0QVx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzQwIEFcdWM3NTggXHVjNTVlXHVhY2ZjIFx1YjRhNFx1YzVkMFx1YzExYyBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFlMzhcdWM3NzRcdWFjMDAgXHVkNjQwXHVjMjE4XHVjNzc0XHViYTc0XHVjMTFjIFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc3NCBCXHVjNzc4IEFcdWM3NTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc3NFx1Yjc4MCBcdWQwNmNcdWFlMzAgXHVjMjFjXHVjNzNjXHViODVjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM4MTVcdWI4MmNcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM2YjRcdWIzNzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgezUsIDEsIDN9XHVjNzU4IFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc0MCAzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgMSAmbGU7IEIgJmxlOyBOKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzkxMVx1YzU1OVx1YWMxMlx1Yzc3NCBCXHVjNzc4IEFcdWM3NTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHR7NH0sIHs3LCAyLCA0fSwgezUsIDcsIDIsIDQsIDN9LCB7NSwgNywgMiwgNCwgMywgMSwgNn08XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTUkVETkpJIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIHNlcXVlbmNlIEEgb2YgaW50ZWdlcnMsIGNvbnRhaW5pbmcgTiBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIE4uIEVhY2ggaW50ZWdlciBhcHBlYXJzIGV4YWN0bHkgb25jZSBpbiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgc3Vic2VxdWVuY2Ugb2YgQSBpcyBhIHNlcXVlbmNlIG9idGFpbmVkIGJ5IHJlbW92aW5nIHNvbWUgKHBvc3NpYmx5IG5vbmUpIG51bWJlcnMgZnJvbSB0aGUgYmVnaW5uaW5nIG9mIEEsIGFuZCB0aGVuIGZyb20gdGhlIGVuZCBvZiBBLiZuYnNwOzxcL3A+XHJcblxyXG48cD5DYWxjdWxhdGUgaG93IG1hbnkgZGlmZmVyZW50IHN1YnNlcXVlbmNlcyBvZiBBIG9mIG9kZCBsZW5ndGggaGF2ZSB0aGVpciBtZWRpYW4gZXF1YWwgdG8gQi4gVGhlIG1lZGlhbiBvZiBhIHNlcXVlbmNlIGlzIHRoZSBlbGVtZW50IGluIHRoZSBtaWRkbGUgb2YgdGhlIHNlcXVlbmNlIGFmdGVyIGl0IGlzIHNvcnRlZC4gRm9yIGV4YW1wbGUsIHRoZSBtZWRpYW4gb2YgdGhlIHNlcXVlbmNlIHs1LCAxLCAzfSBpcyAzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzLCBOICgxICZsZTsgTiAmbGU7IDEwMDAwMCkgYW5kIEIgKDEgJmxlOyBCICZsZTsgTikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBOIGludGVnZXJzIHNlcGFyYXRlZCBieSBzcGFjZXMsIHRoZSBlbGVtZW50cyBvZiBzZXF1ZW5jZSBBLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIHN1YnNlcXVlbmNlcyBvZiBBIHdob3NlIG1lZGlhbiBpcyBCLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIGZvdXIgc3Vic2VxdWVuY2VzIG9mIEEgd2l0aCBtZWRpYW4gNCBhcmUgezR9LCB7NywgMiwgNH0sIHs1LCA3LCAyLCA0LCAzfSBhbmQgezUsIDcsIDIsIDQsIDMsIDEsIDZ9LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d