There are (n+1) rooms arranged in a line, numbered from (1) to (n+1) from left to right. There are also (n) doors numbered from (1) to (n), where the (i)-th door connects rooms (i) and (i+1). Each door (i) has an associated non-negative integer (a_i). You are given a binary string(^{\text{∗}}) (s) of length (n). For each (1 \le i \le n): If (s_i=1), then room (i) initially contains one key. Otherwise, room (i) contains no key. At the beginning of the (0)-th second, you are in room (1), and all doors are closed. For each (k \ge 0), the following events will happen in order in the (k)-th second: At the beginning of the (k)-th second, all doors (j) with (a_j=k) will open. Suppose you are in room (i): If you are not carrying any keys and there is at least one key in room (i), you may pick it up and carry it with you. If you are carrying a key, you may drop it in room (i). If you are not carrying any keys and there is at least one key in room (i), you may pick it up and carry it with you. If you are carrying a key, you may drop it in room (i). At the end of the (k)-th second: You may move to room (i+1). If door (i) is still closed, you have to be carrying a key to move to room (i+1). The key will be consumed after use, and door (i) will open. You may move to room (i-1) if (i>1). You may stay in room (i). You may move to room (i+1). If door (i) is still closed, you have to be carrying a key to move to room (i+1). The key will be consumed after use, and door (i) will open. You may move to room (i-1) if (i>1). You may stay in room (i). For any door, no matter how it was opened (automatically or with a key), it will remain open forever. At any moment, you may carry with you at most one key. Also, even though initially each room contains at most one key, during the process, multip