有一个数组 a，大小为 n，是正整数 1 \sim n 的一种排列，告诉你 n 以及 pos，x 表示 a_{pos} = x（下标从 0 开始）。问对 a 进行二分查找后左端点 left 满足 left > 0，a_{left} = x 即 left = pos 时，可能的 a 有多少个。
思路
对于一个序列 (a_1, a_2, a_3, ..., a_k) 我们对其进行二分查找，找出一个值 x 的位置，其实并不一定需要满足 a 是单调的，只需要满足二分查找所访问到的值，即所有 a_{mid} 组成的序列，按 mid 从小到大排序后单调就行，正确性显然。
已知 a 内共有 n 个数，设其中 pos < x 的有 a 个，pos > x 的有 b 个。易得比 x 小的，即可以放在 x 左边的数有 x - 1 个，比 x 大的，即可以放在 x 右边的数有 n - x 个，也就还剩下 n - a - b - 1 个可以任意排列的数。已知在 k 个不同的数中选 p 个并按一定的顺序排列，不同的方案个数为 A_k^p，那么这道题目的答案也很容易得出，即为
A_a^{x - 1} \cdot A_b^{n - x} \cdot A_{n - a - b - 1}^{n - a - b - 1}
展开后答案就是
时间复杂度 $O(n)$。
## 代码
```cpp
#include <iostream>
using namespace std;
//#define int long long
const int mod = 1e9 + 7;
int n, x, pos, a = 0, b = 0, ans;
signed main() {
cin >> n >> x >> pos;
int l = 0, r = n;//个人习惯，左闭右开
while (r - l > 1) {
int mid = (l + r) / 2;
if (mid <= pos) {
l = mid;
if (mid != pos)
++ a;//x左边的数量加一
}
else
r = mid, ++ b;//x右边的数量加一
}
ans = 1;
for (int i = x - a; i <= x - 1; ++ i)
ans = (ans * i) % mod;
for (int i = n - x - b + 1; i <= n - x; ++ i)
ans = (ans * i) % mod;
for (int i = 1; i <= n - a - b - 1; ++ i)
ans = (ans * i) % mod;
cout << ans;
return 0;
}
```
## Thanks For Reading