시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB66223918942.664%

문제

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}

예제 입력 2

6 3
1 2 4 5 6 3

예제 출력 2

1

예제 입력 3

5 4
1 2 3 4 5

예제 출력 3

2
W3sicHJvYmxlbV9pZCI6IjMwMTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzkxMVx1YzU1OVx1YWMxMiIsImRlc2NyaXB0aW9uIjoiPHA+MVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjQgQVx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM3OTBcdWM1ZjBcdWMyMThcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1ZDU1YyBcdWJjODhcdWM1MjlcdWI5Y2MgXHViNGYxXHVjN2E1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5BXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDAgQVx1Yzc1OCBcdWM1NWVcdWFjZmMgXHViNGE0XHVjNWQwXHVjMTFjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWUzOFx1Yzc3NFx1YWMwMCBcdWQ2NDBcdWMyMThcdWM3NzRcdWJhNzRcdWMxMWMgXHVjOTExXHVjNTU5XHVhYzEyXHVjNzc0IEJcdWM3NzggQVx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjOTExXHVjNTU5XHVhYzEyXHVjNzc0XHViNzgwIFx1ZDA2Y1x1YWUzMCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YzZiNFx1YjM3MFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCB7NSwgMSwgM31cdWM3NTggXHVjOTExXHVjNTU5XHVhYzEyXHVjNzQwIDNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDAsIDEgJmxlOyBCICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjQgQVx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5MTFcdWM1NTlcdWFjMTJcdWM3NzQgQlx1Yzc3OCBBXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+ezR9LCB7NywgMiwgNH0sIHs1LCA3LCAyLCA0LCAzfSwgezUsIDcsIDIsIDQsIDMsIDEsIDZ9PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzAxMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNSRUROSkkiLCJkZXNjcmlwdGlvbiI6IjxwPkNvbnNpZGVyIGEgc2VxdWVuY2UgQSBvZiBpbnRlZ2VycywgY29udGFpbmluZyBOIGludGVnZXJzIGJldHdlZW4gMSBhbmQgTi4gRWFjaCBpbnRlZ2VyIGFwcGVhcnMgZXhhY3RseSBvbmNlIGluIHRoZSBzZXF1ZW5jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBzdWJzZXF1ZW5jZSBvZiBBIGlzIGEgc2VxdWVuY2Ugb2J0YWluZWQgYnkgcmVtb3Zpbmcgc29tZSAocG9zc2libHkgbm9uZSkgbnVtYmVycyBmcm9tIHRoZSBiZWdpbm5pbmcgb2YgQSwgYW5kIHRoZW4gZnJvbSB0aGUgZW5kIG9mIEEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkNhbGN1bGF0ZSBob3cgbWFueSBkaWZmZXJlbnQgc3Vic2VxdWVuY2VzIG9mIEEgb2Ygb2RkIGxlbmd0aCBoYXZlIHRoZWlyIG1lZGlhbiBlcXVhbCB0byBCLiBUaGUgbWVkaWFuIG9mIGEgc2VxdWVuY2UgaXMgdGhlIGVsZW1lbnQgaW4gdGhlIG1pZGRsZSBvZiB0aGUgc2VxdWVuY2UgYWZ0ZXIgaXQgaXMgc29ydGVkLiBGb3IgZXhhbXBsZSwgdGhlIG1lZGlhbiBvZiB0aGUgc2VxdWVuY2UgezUsIDEsIDN9IGlzIDMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMsIE4gKDEgJmxlOyBOICZsZTsgMTAwMDAwKSBhbmQgQiAoMSAmbGU7IEIgJmxlOyBOKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNwYWNlcywgdGhlIGVsZW1lbnRzIG9mIHNlcXVlbmNlIEEuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2Ygc3Vic2VxdWVuY2VzIG9mIEEgd2hvc2UgbWVkaWFuIGlzIEIuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSB0aGlyZCBleGFtcGxlLCB0aGUgZm91ciBzdWJzZXF1ZW5jZXMgb2YgQSB3aXRoIG1lZGlhbiA0IGFyZSB7NH0sIHs3LCAyLCA0fSwgezUsIDcsIDIsIDQsIDN9IGFuZCB7NSwgNywgMiwgNCwgMywgMSwgNn0uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #1 5번