#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
  freopen("../IO/d.in", "r", stdin);
//  freopen("../IO/d.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  int number_of_tests;
  cin >> number_of_tests;

  while (number_of_tests--) {
    int n;
    cin >> n;
    std::vector<int> b(n);
    std::vector<int> used(2 * n);
    for (int &i : b) cin >> i, --i, used[i] = 1;
    std::vector<int> unused;
    unused.reserve(n);
    for (int i = 0; i < 2 * n; ++i) {
      if (!used[i]) unused.push_back(i);
    }
    vector<int> c(n + 1, true);
    int l = -1, r = -1;
    auto check1 = [&](int x) {
      deque<int> dq(unused.begin(), unused.end());
      bool ok = true;
      for (int i = x - 1; i >= 0; --i) {
        ok &= b[i] < dq.back();
        dq.pop_back();
      }
      return ok;
    };
    auto check2 = [&](int x) {
      deque<int> dq(unused.begin(), unused.end());
      bool ok = true;
      for (int i = x; i < n; ++i) {
        ok &= b[i] > dq.front();
        dq.pop_front();
      }
      return ok;
    };
    int lo = -1, hi = n + 1;
    while (hi - lo > 1) {
      int x = (lo + hi) / 2;
      if (check1(x)) {
        lo = x;
      } else {
        hi = x;
      }
    }
    l = 0, r = lo;
    lo = -1, hi = n + 1;
    while (hi - lo > 1) {
      int x = (lo + hi) / 2;
      if (check2(x)) {
        hi = x;
      } else {
        lo = x;
      }
    }
    l = std::max(l, hi);
//    std::cout << l << ' ' << r << '\n';
    std::cout << std::max(0, r - l + 1) << '\n';
  }
  return 0;
}



### Prompt

Please create a solution in cpp to the following problem:

You have 2n integers 1, 2, ..., 2n. You have to redistribute these 2n elements into n pairs. After that, you choose x pairs and take minimum elements from them, and from the other n - x pairs, you take maximum elements.

Your goal is to obtain the set of numbers \\{b_1, b_2, ..., b_n\} as the result of taking elements from the pairs.

What is the number of different x-s (0 ≤ x ≤ n) such that it's possible to obtain the set b if for each x you can choose how to distribute numbers into pairs and from which x pairs choose minimum elements?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains the integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line of each test case contains n integers b_1, b_2, ..., b_n (1 ≤ b_1 < b_2 < ... < b_n ≤ 2n) — the set you'd like to get.

It's guaranteed that the sum of n over test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print one number — the number of different x-s such that it's possible to obtain the set b.

Example

Input


3
1
1
5
1 4 5 9 10
2
3 4


Output


1
3
1

Note

In the first test case, x = 1 is the only option: you have one pair (1, 2) and choose the minimum from this pair.

In the second test case, there are three possible x-s. If x = 1, then you can form the following pairs: (1, 6), (2, 4), (3, 5), (7, 9), (8, 10). You can take minimum from (1, 6) (equal to 1) and the maximum elements from all other pairs to get set b.

If x = 2, you can form pairs (1, 2), (3, 4), (5, 6), (7, 9), (8, 10) and take the minimum elements from (1, 2), (5, 6) and the maximum elements from the other pairs.

If x = 3, you can form pairs (1, 3), (4, 6), (5, 7), (2, 9), (8, 10) and take the minimum elements from (1, 3), (4, 6), (5, 7).

In the third test case, x = 0 is the only option: you can form pairs (1, 3), (2, 4) and take the maximum elements from both of them.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
  freopen("../IO/d.in", "r", stdin);
//  freopen("../IO/d.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  int number_of_tests;
  cin >> number_of_tests;

  while (number_of_tests--) {
    int n;
    cin >> n;
    std::vector<int> b(n);
    std::vector<int> used(2 * n);
    for (int &i : b) cin >> i, --i, used[i] = 1;
    std::vector<int> unused;
    unused.reserve(n);
    for (int i = 0; i < 2 * n; ++i) {
      if (!used[i]) unused.push_back(i);
    }
    vector<int> c(n + 1, true);
    int l = -1, r = -1;
    auto check1 = [&](int x) {
      deque<int> dq(unused.begin(), unused.end());
      bool ok = true;
      for (int i = x - 1; i >= 0; --i) {
        ok &= b[i] < dq.back();
        dq.pop_back();
      }
      return ok;
    };
    auto check2 = [&](int x) {
      deque<int> dq(unused.begin(), unused.end());
      bool ok = true;
      for (int i = x; i < n; ++i) {
        ok &= b[i] > dq.front();
        dq.pop_front();
      }
      return ok;
    };
    int lo = -1, hi = n + 1;
    while (hi - lo > 1) {
      int x = (lo + hi) / 2;
      if (check1(x)) {
        lo = x;
      } else {
        hi = x;
      }
    }
    l = 0, r = lo;
    lo = -1, hi = n + 1;
    while (hi - lo > 1) {
      int x = (lo + hi) / 2;
      if (check2(x)) {
        hi = x;
      } else {
        lo = x;
      }
    }
    l = std::max(l, hi);
//    std::cout << l << ' ' << r << '\n';
    std::cout << std::max(0, r - l + 1) << '\n';
  }
  return 0;
}



```