만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

증가 수열

면접 대비

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

요약
양의 정수 수열 a가 주어질 때, 각 b_i가 a_i와 다르면서 엄격히 증가하는 수열의 마지막 값 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