Given an array A[1 . . . n] of n distinct numbers (i.e., no two numbers of A are equal), design an O(n 2 ) time dynamic programming algorithm to find a longest monotonically increasing subsequence of A. Your algorithm needs to report not only the length but also the actual longest subsequence (i.e., report all elements in the subsequence). Here is a formal definition of a longest monotonically increasing subsequence of A (refer to the example given below). First of all, a subsequence of A is a subset of numbers of A such that if a number a appears in front of another number b in the subsequence, then a is also in front of b in A. Next, a subsequence of A is monotonically increasing if for any two numbers a and b such that a appears in front of b in the subsequence, a is smaller than b. Finally, a longest monotonically increasing subsequence of A refers to a monotonically increasing subsequence of A that is longest (i.e., has the maximum number of elements).For example, if A = {20, 5, 14, 8, 10, 3, 12, 7, 16}, then a longest monotonically increasing subsequence is 5, 8, 10, 12, 16. Note that the answer may not be unique, in which case you only need to report one such longest subsequence.