Cubicle Preferences

Problem Statement

Cubicle Preferences There are `2n` employees with IDs `1` through `2n`. They must be paired into `n` cubicles. Every cubicle has a window seat and an aisle seat. After the pairs are formed, choose an integer `x`. In exactly `x` cubicles the employee with the smaller ID occupies the window seat; in all other cubicles the employee with the larger ID occupies the window seat. You are given the IDs of the window-seat employees in increasing order. Count how many values of `x` from `0` through `n` can produce exactly this set of window-seat employees. Input The first line contains `T` (`1 <= T <= 1000`). Each test case contains `n` (`1 <= n <= 2*10^5`), followed by `n` increasing integers `b[1..n]` (`1 <= b[1] < ... < b[n] <= 2n`). The sum of `n` over all tests is at most `2*10^5`. Output For each test case print the number of feasible values of `x`. Notes For a fixed `x`, it is enough to consider the first `x` listed IDs as the smaller members of their pairs and the