증가 수열

시간 제한1초메모리 제한1024 MB

요약
각 테스트 케이스에서 b[i]가 a[i]와 다르면서 순증가하는 양의 정수 수열 b를 만들고, 마지막 원소 b[n]의 최솟값을 구한다.
난이도

쉬움10점 중 3점

유형
그리디, 구현
정답자
아직 제출이 없습니다

문제

수열 a_1,a_2,…,a_na\_{1}, a\_{2}, \ldots, a\_{n}이 주어진다. 다음 조건을 만족하는 수열 b_1,b_2,…,b_nb\_{1}, b\_{2}, \ldots, b\_{n}을 좋은 수열이라고 정의한다:

  • b_ib\_{i}는 양의 정수이다(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}이다.

좋은 수열 b_1,b_2,…,b_nb\_{1}, b\_{2}, \ldots, b\_{n}에 대하여, b_nb\_{n}의 최솟값을 구하여라.

입력

각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 tt가 주어진다(1≤t≤1001 \le t \le 100). 다음 줄부터 각각의 테스트 케이스가 주어진다.

각각의 테스트 케이스의 첫 번째 줄에 정수 nn이 주어진다 (1≤n≤1001 \le n \le 100).

두 번째 줄에 nn개의 정수 a_1,a_2,…,a_na\_1, a\_2, \ldots, a\_n이 공백으로 구분되어 주어진다 (1≤a_i≤1091 \le a\_i \le 10^{9}).

출력

각각의 테스트 케이스마다 정답을 출력한다.

힌트

첫 번째 테스트 케이스에서, b=\[2,4,5,7,8]b = \[2, 4, 5, 7, 8]은 좋은 수열이다. b_5<8b\_{5} < 8인 좋은 수열 bb가 없음을 증명할 수 있다.

두 번째 테스트 케이스에서, b=\[1,2,3,4]b = \[1, 2, 3, 4]가 가능하다.

세 번째 테스트 케이스에서, b=\[2]b = \[2]가 가능하다.

예제1

  1. 예제 1

    입력
    3
    5
    1 3 2 6 7
    4
    2 3 4 5
    1
    1
    
    예상 출력
    8
    4
    2