시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 72 22 20 38.462%

문제

과외맨은 배트맨, 스파이더맨, 슈퍼맨과 같은 슈퍼 히어로를 따라하는 한국의 대표 영웅이다. 오늘은 스파이더맨을 따라해보려고 한다. 과외맨은 고층 건물의 옥상을 점프하면서 돌아다니려고 한다.

고층 건물은 총 N개가 있고, 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 매겨져 있다. 지금 과외맨은 K번 건물 위에 있다. 과외맨은 아직 힘이 많이 부족한다. 따라서, 현재 있는 건물의 왼쪽 또는 오른쪽 건물로만 점프해서 이동할 수 있다. 또, 지금 자신이 있는 건물의 높이보다 높지 않은 빌딩으로만 이동할 수 있다.

이런 과외맨을 도와주고 위해서 상근이는 일부 건물의 옥상에 트램폴린을 설치해 놓았다. 과외맨이 트램폴린을 이용해 점프를 한다면 다른 모든 건물로 이동할 수 있고, 건물의 높이와 상관없이 이동할 수 있다.

과외맨이 방문할 수 있는 서로 다른 건물의 개수의 최댓값을 구하는 프로그램을 작성하시오. 과외맨은 점프를 K번 빌딩에서 시작한다. 같은 건물을 여러 번 방문할 때도, 방문한 건물의 개수는 한 개로 센다. 

입력

첫째 줄에 건물의 수 N과 점프를 시작하는 건물의 번호 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N)

둘째 줄에는 106보다 작은 N개의 정수가 주어진다. 이 정수는 건물의 높이이며, 1번 건물부터 순서대로 주어진다.

셋째 줄에는 '.' 또는 'T'로 이루어진 N개의 문자가 주어진다. i번째 문자가 'T'인 경우에는 i번 건물의 옥상에 트램폴린이 설치되어 있는 것이다.

출력

첫째 줄에 과외맨이 방문할 수 있는 서로 다른 건물 개수의 최댓값을 출력한다.

예제 입력 1

10 1
10 7 3 1 1 9 8 2 4 10
..T..T....

예제 출력 1

7

힌트

1 -> 2 -> 3 -> 6 -> 10 -> 9 -> 8

W3sicHJvYmxlbV9pZCI6IjI3OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI3YThcdWQzZjRcdWI5YjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0MCBcdWJjMzBcdWQyYjhcdWI5ZTgsIFx1YzJhNFx1ZDMwY1x1Yzc3NFx1YjM1NFx1YjllOCwgXHVjMjg4XHVkMzdjXHViOWU4XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyODhcdWQzN2MgXHVkNzg4XHVjNWI0XHViODVjXHViOTdjIFx1YjUzMFx1Yjc3Y1x1ZDU1OFx1YjI5NCBcdWQ1NWNcdWFkNmRcdWM3NTggXHViMzAwXHVkNDVjIFx1YzYwMVx1YzZjNVx1Yzc3NFx1YjJlNC4gXHVjNjI0XHViMjk4XHVjNzQwIFx1YzJhNFx1ZDMwY1x1Yzc3NFx1YjM1NFx1YjllOFx1Yzc0NCBcdWI1MzBcdWI3N2NcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHVhY2UwXHVjZTM1IFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWM2MjVcdWMwYzFcdWM3NDQgXHVjODEwXHVkNTA0XHVkNTU4XHViYTc0XHVjMTFjIFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJjOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1Y2UzNSBcdWFjNzRcdWJiM2NcdWM3NDAgXHVjZDFkIE5cdWFjMWNcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjOWMwXHVhZTA4IFx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0MCBLXHViYzg4IFx1YWM3NFx1YmIzYyBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHVjNTQ0XHVjOWMxIFx1ZDc5OFx1Yzc3NCBcdWI5Y2VcdWM3NzQgXHViZDgwXHVjODcxXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWI2MTBcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWM3NFx1YmIzY1x1Yjg1Y1x1YjljYyBcdWM4MTBcdWQ1MDRcdWQ1NzRcdWMxMWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHVjOWMwXHVhZTA4IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YmNmNFx1YjJlNCBcdWIxOTJcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmU0Y1x1YjUyOVx1YzczY1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2YwIFx1YWNmY1x1YzY3OFx1YjllOFx1Yzc0NCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWFjZTAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3N2NcdWJkODAgXHVhYzc0XHViYjNjXHVjNzU4IFx1YzYyNVx1YzBjMVx1YzVkMCBcdWQyYjhcdWI3YThcdWQzZjRcdWI5YjBcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTc0IFx1YjE5M1x1YzU1OFx1YjJlNC4gXHVhY2ZjXHVjNjc4XHViOWU4XHVjNzc0IFx1ZDJiOFx1YjdhOFx1ZDNmNFx1YjliMFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWIyZTRcdWI5NzggXHViYWE4XHViNGUwIFx1YWM3NFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWMwYzFcdWFkMDBcdWM1YzZcdWM3NzQgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmY1x1YzY3OFx1YjllOFx1Yzc3NCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NDAgXHVjODEwXHVkNTA0XHViOTdjIEtcdWJjODggXHViZTRjXHViNTI5XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWI1NGNcdWIzYzQsIFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWFjNzRcdWJiM2NcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1ZDU1YyBcdWFjMWNcdWI4NWMgXHVjMTNjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjNzRcdWJiM2NcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVjODEwXHVkNTA0XHViOTdjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWFjNzRcdWJiM2NcdWM3NTggXHViYzg4XHVkNjM4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAzMDAsMDAwLCAxICZsZTsgSyAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMTA8c3VwPjY8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yzc3NFx1YmE3MCwgMVx1YmM4OCBcdWFjNzRcdWJiM2NcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAmIzM5Oy4mIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTtUJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE5cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWFjMDAgJiMzOTtUJiMzOTtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IGlcdWJjODggXHVhYzc0XHViYjNjXHVjNzU4IFx1YzYyNVx1YzBjMVx1YzVkMCBcdWQyYjhcdWI3YThcdWQzZjRcdWI5YjBcdWM3NzQgXHVjMTI0XHVjZTU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjZmNcdWM2NzhcdWI5ZThcdWM3NzQgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjNzRcdWJiM2MgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjEgLSZndDsgMiAtJmd0OyAzIC0mZ3Q7IDYgLSZndDsgMTAgLSZndDsgOSAtJmd0OyA4PFwvcD5cclxuXHJcbjxwPjxpZnJhbWUgZnJhbWVib3JkZXI9XCIwXCIgaGVpZ2h0PVwiNDgwXCIgc3JjPVwiaHR0cDpcL1wvd3d3LnlvdXR1YmUuY29tXC9lbWJlZFwvX3VZeDEzVFBtLUFcIiB3aWR0aD1cIjg1M1wiPjxcL2lmcmFtZT48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3OTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUUkFNUE9MSU4iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBtYW55IGFjdGlvbiBzdXBlcmhlcm9lcyBvdXQgdGhlcmU6IEJhdG1hbiwgU3BpZGVybWFuLCBTdXBlcm1hbiwgSWNhbnR3cml0ZW1hbiBldGMuIEFtb25nIHRoZW0sIHRoZXJlIGlzIG9uZSBnZW50bGVtYW4gY2FsbGVkIEtpY2thc3MuIFRvZGF5IGhlIHdhbnRzIHRvIG1pbWljIFNwaWRlcm1hbiwgc28gaGUgaGFzIGNob3NlbiBhIHJvdyBvZiB0YWxsIHNreXNjcmFwZXJzIHRvIGp1bXAgYXJvdW5kIG9uLjxcL3A+XHJcblxyXG48cD5TcGVjaWZpY2FsbHksIGhlIGhhcyBjaG9zZW4gYSBzZXF1ZW5jZSBvZiBOIHNreXNjcmFwZXJzIG51bWJlcmVkIDEgdGhyb3VnaCBOIGZyb20gbGVmdCB0byByaWdodC4gSGUgaXMgaW5pdGlhbGx5IGxvY2F0ZWQgb24gdGhlIEt0aCBza3lzY3JhcGVyLiBVbmZvcnR1bmF0ZWx5LCBLaWNrYXNzIGhhcyB2ZXJ5IGxpbWl0ZWQgcG93ZXJzLCBhbmQgY2FuIHRoZXJlZm9yZSBqdW1wIG9ubHkgdG8gdGhlIGFkamFjZW50IHNreXNjcmFwZXIgdG8gdGhlIGxlZnQgb3IgcmlnaHQsIGFuZCBvbmx5IGlmIHRoYXQgc2t5c2NyYXBlciYjMzk7cyBoZWlnaHQgaXMgbm90IGdyZWF0ZXIgdGhhbiB0aGUgaGVpZ2h0IG9mIHRoZSBza3lzY3JhcGVyIGhlIGlzIGN1cnJlbnRseSBvbi4gSG93ZXZlciwgYW50aWNpcGF0aW5nIHRoaXMgYW5kIG5vdCB3YW50aW5nIHRvIGxvb2sgd2VhaywgaGUgaGFzIHBvc2l0aW9uZWQgdHJhbXBvbGluZXMgb24gdG9wIG9mIHNvbWUgc2t5c2NyYXBlcnMsIGFuZCBmcm9tIHRoZXNlIHNreXNjcmFwZXJzIGhlIGNhbiBqdW1wIG9udG8gYW55IG90aGVyIHNreXNjcmFwZXIsIG5vIG1hdHRlciBob3cgdGFsbCBvciB3aGVyZSB0aGF0IHNreXNjcmFwZXIgaXMuPFwvcD5cclxuXHJcbjxwPkZpbmQgdGhlIG1heGltdW0gbnVtYmVyIG9mIGRpZmZlcmVudCBza3lzY3JhcGVycyBLaWNrYXNzIGNhbiB2aXNpdCBpbiBhIGNoYWluIG9mIGp1bXBzIHN0YXJ0aW5nIGZyb20gdGhlIHNreXNjcmFwZXIgbnVtYmVyZWQgSy4gSWYgYSBza3lzY3JhcGVyIGlzIHZpc2l0ZWQgbW9yZSB0aGFuIG9uY2UsIHdlIHN0aWxsIGNvdW50IGl0IG9ubHkgb25jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TW9yZW92ZXIsIHNreXNjcmFwZXIgSyBpcyBjb3VudGVkIGV2ZW4gaWYgd2UgbmV2ZXIgcmV0dXJuIHRvIGl0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHR3byBpbnRlZ2VycyBOIGFuZCBLICgzICZsZTsgTiAmbGU7IDMwMCAwMDAsIDEgJmxlOyBLICZsZTsgTiksIHRoZSB0b3RhbCBudW1iZXIgb2Ygc2t5c2NyYXBlcnMgYW5kIHRoZSBzdGFydGluZyBza3lzY3JhcGVyLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIGludGVnZXJzIGxlc3MgdGhhbiAxMDxzdXA+NjxcL3N1cD4sIHRoZSBoZWlnaHRzIG9mIHNreXNjcmFwZXJzIGluIG9yZGVyIGZyb20gbGVmdCB0byByaWdodC48XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBOIGNoYXJhY3RlcnMgJiMzOTsuJiMzOTsgb3IgJiMzOTtUJiMzOTsuIElmIHRoZSBpdGggY2hhcmFjdGVyIGlzICYjMzk7VCYjMzk7LCB0aGVuIHRoZXJlIGlzIGEgdHJhbXBvbGluZSBwb3NpdGlvbmVkIG9uIHRoZSB0b3Agb2Ygc2t5c2NyYXBlciBpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1heGltdW0gbnVtYmVyIG9mIHZpc2l0ZWQgc2t5c2NyYXBlcnMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD50aGUgc2VxdWVuY2Ugb2YgdmlzaXRlZCBza3lzY3JhcGVycyBjb3VsZCBiZSB0aGUgZm9sbG93aW5nOiZuYnNwOzxcL3A+XHJcblxyXG48cD4xIC0mZ3Q7IDIgLSZndDsgMyAtJmd0OyA2IC0mZ3Q7IDEwIC0mZ3Q7IDkgLSZndDsgOC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==