Count a value in a list

Problem

Write a recursive function that counts how many times a target appears in a list. Pass an index, not a slice. Read the list and the target.

Input: Line 1: n. Line 2: n integers separated by spaces. Line 3: the target integer.
Output: One integer: how many times the target appears.
Constraints: 1 ≤ n ≤ 500
-1000 ≤ each value, target ≤ 1000

Example

Input

5
3 1 3 3 2
3

Output

3 appears three times.

Try the problem first. Open one hint at a time.

Hint 1

The base case is when the index reaches the end.

Hint 2

Add 1 when the current item equals the target, then move to the next index.

Write your Python code, run it on the examples and submit it to hidden tests.