Increasing Sequence
InterviewTime limit1sMemory limit1024 MB
Given a sequence a, find the smallest possible last value b_n of a strictly increasing positive sequence where each b_i differs from a_i.
- Level
Easy3 of 10
- Topics
- Greedy, Implementation
- Solved
- No attempts yet
Problem
Given a sequence , a sequence is called a good sequence if it satisfies the following conditions:
- is a positive integer ().
- ().
- .
Find the minimum possible value of over all good sequences .
Input
Each input consists of multiple test cases. The first line contains the number of test cases (). Each test case follows on the next lines.
The first line of each test case contains an integer ().
The second line contains integers separated by spaces ().
Output
For each test case, print the answer.
Hint
In the first test case, is a good sequence. It can be proven that no good sequence has . In the second test case, is possible. In the third test case, is possible.