TopCoder

Thumb d4pea70

$$\lim_{\text{#AC} \rightarrow -\infty} $$

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

21.6% (16/74)

Description

你,纏流子,因為打不贏學生會長鬼龍院,所以你打算落跑。


(圖為學生會長鬼龍院大人玉照)

因為平地太容易被追到所你決定在一排房子的屋頂上跑來跑去,以擺脫掉追兵。

你現在在一排房子,總共有n棟,編號由左至右分別為$1,2,,,n$。你一開始在第k棟房子屋頂上。不幸的是,你太廢了,只能跳到相鄰而且不能比現在高的屋頂上。雖然你很廢,但你卻有事先在某些屋頂上準備了噴射裝置,噴射裝置可以允許你噴射到任一棟房子屋頂上,不管多高或多遠。而為了避免埋伏,所以你希望可以走過越多相異的房子越好。

請你計算出你最多可以經過幾個相異房子,一開始的大樓也算在經過的大樓中。

Input Format

第一行有兩個整數 $N$ 和 $K(3≤N≤300000,1≤K≤N)$,分別代表房子數和一開始所在的房子編號 $K$。

第二行有 $N$ 個小於 1e6 的整數,由左而右依序代表各房子的高度。

第三行由'.'和'T'構成,如果某一編號為'T',則代表該編號房子上有噴射裝置。

Output Format

輸出你最多可以經過幾棟相異房子。

Sample Input

sample input #1:
6 4
12 16 16 16 14 14
.T....

sample input #2:
10 1
10 7 3 1 1 9 8 2 4 10
..T..T....

Sample Output

sample output #1:
5

sample output #2:
7

Hints

對於第二筆範例測資,你經過的房子依序為:
1 → 2 → 3 → 6 → 10 → 9 → 8

Problem Source

STEP5 0141-噴射裝置

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 131072 262144 9
9 1000 131072 262144 10