408874: GYM103371 B Cilantro

Junwon Kim runs a Vietnamese noodle restaurant in Sharosu-gil, a street near Seoul National University which is home to trendy gourmets.

Junwon sells two kinds of noodles: one with cilantro, and one without. Today, he will cook $$$n$$$ batches of noodles. Junwon has a fixed schedule cooking the noodles, represented by a length-$$$n$$$ string $$$S$$$. If the $$$i$$$-th character of $$$S$$$ is Y, then the $$$i$$$-th dish Junwon cooks will have cilantro. Otherwise, it will not have cilantro.

Since Junwon's restaurant is very famous, $$$n$$$ customers are already waiting in line to experience his ultimate noodles. The customers' preferences are also represented by a length-$$$n$$$ string $$$T$$$. If the $$$i$$$-th character of $$$T$$$ is Y, then the $$$i$$$-th customer wants noodles with cilantro. Otherwise, the $$$i$$$-th customer wants noodles without cilantro.

Junwon has to serve each customer in a first-come-first-serve manner. In this regard, the $$$i$$$-th customer should receive the $$$i$$$-th dish. However, this may violate the preference of the customer. To solve this problem, Junwon installed noodle storage. The noodle storage stores noodles as a stack: you can only access the noodles that were inserted most recently. Junwon will put all cooked noodles right into the noodle storage, and serve the noodles only from the noodle storage. If Junwon decided to serve the noodles from the storage, then he must serve the topmost noodles - he cannot rearrange the noodles in any way after they are added to the stack.

To summarize, when the $$$i$$$-th customer orders noodles, Junwon will cook $$$0$$$ or more batches of noodles, put them in the noodle storage, and then serve the noodle at the top of the noodle storage. Junwon should schedule the cooking in a way such that every customer receives the noodles that they want. Note that Junwon can't cook more than $$$n$$$ noodles.

Today is a bad day for Junwon, because the infamous Jaehyun Koo is the first customer today. Jaehyun is known for his toxic online food reviews, where he sometimes goes so far that the restaurant should stop creating shit problems food and go out of business.

Junwon thinks the quality of his noodles are uneven. Therefore, he wants to know which dishes have a possibility to be served to Jaehyun, while satisfying the condition that every customer receives a menu that they ordered. Please print the sum of indices of dishes that can be served to Jaehyun. Dishes are 1-indexed. If there is no way to serve dishes, output $$$0$$$.

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5\,000\,000)$$$.

The next line contains a length-$$$n$$$ string $$$S$$$. All characters of $$$S$$$ are either Y or N.

The next line contains a length-$$$n$$$ string $$$T$$$. All characters of $$$T$$$ are either Y or N.

Output a single integer denoting the answer of the problem.

3
YNN
NNY

5

4
NYNY
YNNY

2