I am trying to solve this problem, but so far no luck. Can anybody show me the correct approach. I know that it is possible to find longest increasing subsequence in O(n) time.

Problem statement:

Given a sequence of integers, find the maximum difference between first and last element of the longest increasing subsequence.

Input:

First line contains T, number of test cases followed by T test cases. For each test case first line contains an integer N , the next line contains sequence of N integers.

Constraints:

T <  = 100

1 <  = N <  = 10000

All numbers in the sequence will fit into 64-bit integer