Write pseudocode for linear search, assuming that the input list is already sorted, and also return the would-be index for the key if the key is not in the list. Note: Your algorithm should take advantage of the fact that the list is sorted, but still looks for the value by comparing the list elements one by one with the value.

Problem: Linear Search in a sorted (in descending order) list Input: list A[0...n-1], i.e., list index starts from 1

 n: the length of list A 

v: the value we are searching A[0...n-1] for and A[0]>=A[1]>=...>=A[n-1]

Output: if v appears in list A[0...n-1], return the index of the its first appearance

if v does not appear in the list, return the negation of the would-be index of v (i.e., the index of v if v is inserted into the sorted list and the descending order is to be maintained)

for example, 1) list A=[9,6,4,1], n=4, v=5, the function shall return -2 2) list A=[9,6,5,2], n=4, v=6, the function shall return 1

 Algorithm: LinearSearch (A, n, v)