NDS - Increasing numbers
Subham and Dewang both are playing with numbers. Subham gives Dewang an array of numbers and asks him to tell the minimum possible last number of a increasing sequence of length L.
Note: Check the sample I/O for more clarity.
Input
Input consists of number of test cases T. Each test case contains size of array i.e N. Next line contains N space separated elements of array. Next line contains length of the increasing sequence i.e. L.
Constraignts
1 ≤ T ≤ 100
0 ≤ N ≤ 106
0 ≤ a[i] ≤ 106
Output
You have to print the minimum possible last number of a sequence and if their is no increasing sequence of length L, then print "-1" without the quotes.
Example
Input: 1 7 9 7 2 5 4 11 12 3 Output: 11
Explanation
In sample input, possible increasing sequences of length L = 3 are (9, 11, 12), (7, 11, 12), (2, 5, 11), (2, 4, 11), (2, 5, 12), (2, 4, 12), (2, 11, 12), (5, 11, 12), (4, 11, 12) and the minimum last number is 11 for the sequences (2, 5, 11) and (2, 4, 11). Hence, the answer is 11.
hide comments
Simes:
2022-11-06 00:55:13
@maestro1900: don't assume you passed test cases 1-6, SPOJ doesn't work like that. |
|
maestro1900:
2022-11-05 12:17:41
what is testcase 7?
|
|
gugakatamadze:
2022-10-27 21:49:13
Don't forget to output -1 when L > N |
|
annaadu:
2022-10-24 11:04:57
me-7 test case, vichxubeeebt |
|
savan000:
2022-06-19 19:38:39
O(n^2) complexity solution will be accepted. Strictly Increasing. use Patience sort(full algo not needed).
|
|
princemishra:
2022-01-06 15:10:41
no use of binary search :( ///
|
|
fuadul_hasan:
2021-12-31 04:33:48
easy BIT problem.... but took me hard time though. :( |
|
kn_1111:
2021-12-05 03:20:14
For those getting WA, try to make LIS but not "strictly" increasing |
|
priyankarai:
2021-06-02 12:20:14
I did it with LIS concept. Can someone tell me how to think of it using segment tree. |
|
csd_123:
2020-10-18 13:46:30
gettig error in test case 7 using LIS
|
Added by: | Buttman |
Date: | 2016-07-06 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |