Under construction

Still being built. Things may change

Increasing Sequence

Interview

Time limit1sMemory limit1024 MB

Summary
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_1,a_2,…,a_na\_{1}, a\_{2}, \ldots, a\_{n}, a sequence b_1,b_2,…,b_nb\_{1}, b\_{2}, \ldots, b\_{n} is called a good sequence if it satisfies the following conditions:

  • b_ib\_{i} is a positive integer (i=1,2,…,ni = 1, 2, \ldots, n).
  • b_i≠a_ib\_{i} \neq a\_{i} (i=1,2,…,ni = 1, 2, \ldots, n).
  • b_1<b_2<…<b_nb\_{1} < b\_{2} < \ldots < b\_{n}.

Find the minimum possible value of b_nb\_{n} over all good sequences b_1,b_2,…,b_nb\_{1}, b\_{2}, \ldots, b\_{n}.

Input

Each input consists of multiple test cases. The first line contains the number of test cases tt (1≤t≤1001 \le t \le 100). Each test case follows on the next lines.

The first line of each test case contains an integer nn (1≤n≤1001 \le n \le 100).

The second line contains nn integers a_1,a_2,…,a_na\_1, a\_2, \ldots, a\_n separated by spaces (1≤a_i≤1091 \le a\_i \le 10^{9}).

Output

For each test case, print the answer.

Hint

In the first test case, b=[2,4,5,7,8]b = [2, 4, 5, 7, 8] is a good sequence. It can be proven that no good sequence bb has b_5<8b\_{5} < 8. In the second test case, b=[1,2,3,4]b = [1, 2, 3, 4] is possible. In the third test case, b=[2]b = [2] is possible.

Examples1

  1. Example 1

    Input
    3
    5
    1 3 2 6 7
    4
    2 3 4 5
    1
    1
    
    Expected output
    8
    4
    2