Extend the program in Figure 1 to implement a linear search. Your answer must be written in C#.

string[] cities = {"London", "Paris", "Rome",
                  "Berlin", "Tokyo", "Sydney"};

Figure 1

The program should ask the user to enter a city and perform a linear search on the array cities to check if that city is present in the list.

The program must:

• prompt the user to input a city name to search for
• output the message Found if the city is present in the array
• output the message Not Found if the city is not present in the array

You must write your own linear search routine and not use any built-in search functions or methods available in C#.

You should use meaningful variable names and correct C# syntax in your answer.