lower_bound 和 upper_bound：在排好序的数组上找

// STL 专题 · 二分三件套 —— lower_bound 和 upper_bound
//
// ★ 一句话钉死：
//     lower_bound(v, x) = 第一个 >= x 的位置
//     upper_bound(v, x) = 第一个 >  x 的位置
//
// ⚠⚠ 三件事必须同时知道，缺一件就会写错：
//   ① **前提**：v 已经从小到大排好 —— 这是正确性问题，不是性能问题
//   ② **返回的是位置不是下标** —— 当下标用要再减 v.begin()
//   ③ 找不到时返回 v.end()，那是**合法答案**不是错误
//
// ⚠ 输入第一行 n，第二行 n 个**升序**整数，第三行 x。

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, x;
  cin >> n;
  vector<int> v(n);
  for (int &t : v) cin >> t;
  cin >> x;

  cout << "v = ";
  for (int t : v) cout << t << ' ';
  cout << "   找 x = " << x << "\n\n";

  // ── lower_bound：第一个 >= x 的位置 ────────────────────────────
  // ⚠ 减 v.begin() 才是下标。漏了它得到的是一个内存偏移量，不会崩，只是答案全错。
  int lo = lower_bound(v.begin(), v.end(), x) - v.begin();

  // ── upper_bound：第一个 > x 的位置 ────────────────────────────
  int hi = upper_bound(v.begin(), v.end(), x) - v.begin();

  cout << "lower_bound(v, " << x << ") = 下标 " << lo << "   （第一个 >= " << x << "）\n";
  if (lo == n) cout << "   它等于 v.end()：没有比 " << x << " 大的了 —— 这是合法答案\n";
  else         cout << "   那里是 " << v[lo] << '\n';

  cout << "\nupper_bound(v, " << x << ") = 下标 " << hi << "   （第一个 >  " << x << "）\n";
  if (hi == n) cout << "   它也等于 v.end()\n";
  else         cout << "   那里是 " << v[hi] << '\n';

  // ★★ 两个函数的差就是一个区间里有多少个数 —— 这是最常考的一问。
  cout << "\n所以 [" << x << ", " << x << "] 里有 " << hi - lo << " 个数"
       << "   ← 就是「等于 " << x << " 的有几个」\n";
  return 0;
}

// STL 专题 · 二分三件套 —— 数一数有多少个数落在区间里
//
// ★ OI 里最常问的一问，而答案就是两个函数相减：
//
//     [L, R] 里几个 = upper_bound(R) - lower_bound(L)
//     [L, R) 里几个 = lower_bound(R) - lower_bound(L)
//
// ⚠ 输入第一行 n L R，第二行 n 个**升序**整数。

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, L, R;
  cin >> n >> L >> R;
  vector<int> v(n);
  for (int &t : v) cin >> t;

  cout << "v = ";
  for (int t : v) cout << t << ' ';
  cout << "\n\n";

  // ① [L, R] 闭区间 —— 两个函数的方向不一样
  int closed = upper_bound(v.begin(), v.end(), R) - lower_bound(v.begin(), v.end(), L);

  // ② [L, R) 左闭右开 —— 两边都用 lower_bound
  int leftClosed = lower_bound(v.begin(), v.end(), R) - lower_bound(v.begin(), v.end(), L);

  cout << "[" << L << ", " << R << "]  里有 " << closed << " 个   ← 上界用 upper_bound\n";
  cout << "[" << L << ", " << R << ")  里有 " << leftClosed << " 个   ← 上界用 lower_bound\n";
  cout << "\n差了 " << closed - leftClosed << " 个 —— 那几个就是刚好等于 " << R << " 的\n";

  // ③ 顺手：数一数 <= x 的有几个
  int x = 7;
  int le = upper_bound(v.begin(), v.end(), x) - v.begin();
  cout << "\n顺便：<= " << x << " 的有 " << le
       << " 个   ← 公式是 upper_bound(" << x << ") - v.begin()\n";

  return 0;
}