Intuit OA 2023 - Lazy Chef

Chef enters the kitchen which consists of N linear blocks where each block contains only 1 ingredient from a list of ingredients.
Chef has to prepare the dish using one ingredient I. To prepare the dish D, the first task for Chef is to group blocks of all I ingredients together.
Chef needs to achieve this task by only swapping adjacent blocks with one another. One swap is equivalent to one valid move. Since the chef is lazy, can you help him determine the minimum number of moves in which he can complete this task?

Input Format

• The first line contains N, denoting the number of blocks in the kitchen.
• The second line contains N space-separated characters, where the (i)-th character represents the ingredient on the (i)-th block.
• The third line contains a character I, denoting the ingredient required to prepare dish D.

Output Format

Print the minimum number of moves in which Chef can complete this task.

Constraints

• (1 <= N <= 100,000)
• There is at least one occurrence of I on the shelf.
• One swap is equivalent to one valid move.

Example

Sample Input:

7
H D H S A H S
H

Sample Output:

3

Explanation:

Here are the set of moves required:

1. Move 1 - Swapping element at index 0 and 1:
   D H H S A H S
2. Move 2 - Swapping element at index 4 and 5:
   D H H S H A S
3. Move 3 - Swapping element at index 3 and 4:
   D H H H S A S

Thus, the minimum number of moves is 3.