反证法。

假设每个抽屉包含的物体数量都少于 \(2\) 个（即最多包含 \(1\) 个），那么 \(n\) 个抽屉所能容纳的物体总数最多为 \(n \times 1 = n\) 个，这与总共有 \(n+1\) 个物体的已知条件相矛盾。因此，假设不成立，原命题成立。

将这 \(10\) 个数配对成 \(5\) 个集合（抽屉）\(\{ 1,10 \}, \{ 2,9 \}, \{ 3,8 \}, \{ 4,7 \}, \{ 5,6 \}\)，共 \(5\) 个抽屉。从 \(10\) 个数中取出 \(6\) 个数（\(6\) 个物体），根据抽屉原理，至少有两个数来自于同一集合。而每个集合中两数之和均为 \(11\)，故必有两个数的和等于 \(11\)。

考虑每一列的 \(3\) 个格子的颜色，因为只有 \(2\) 种颜色，根据抽屉原理，每列的 \(3\) 个格子中至少有 \(2\) 个格子颜色相同（同红或同蓝）。

每一列中“相同颜色的两个位置”共有 \(C_3^2 = 3\) 种位置组合 \((1,2), (2,3), (1,3)\)，且颜色有 \(2\) 种（红/蓝），因此位置组合与颜色的形态共有 \(3 \times 2 = 6\) 种（即 \(6\) 个抽屉）。

网格一共有 \(7\) 列（\(7\) 个物体），根据抽屉原理，在这 \(7\) 列中，至少有 \(2\) 列具有完全相同的“同色位置与颜色”形态，这两列中对应的 \(4\) 个角上的方格就构成了一个四角同色的矩形。

给定的 \(n+1\) 个整数 \(a_1, a_2, \dots, a_{n+1}\) 即 \(n+1\) 个物体，按照除以 \(n\) 的余数分类。任何整数除以 \(n\) 的余数只能是 \(0,1,2, \dots, n-1\)，共 \(n\) 种可能的余数（共 \(n\) 个抽屉）。把 \(n+1\) 个整数按其余数放入 \(n\) 个抽屉中，根据抽屉原理，必有两个整数 \(a_i\) 和 \(a_j \ (i \ne j)\) 落在同一个抽屉中，即它们除以 \(n\) 的余数相同。余数相同，则它们的差 \(a_i-a_j\) 必能被 \(n\) 整除。

考虑 \(n\) 个前缀和 \(S_1, S_2, \dots, S_n\)，若其中某个 \(S_k \equiv 0 \pmod{n}\)，则前 \(k\) 个数之和就能被 \(n\) 整除，命题得证。

若所有 \(S_k\) 都不能被 \(n\) 整除，则它们模 \(n\) 的余数只能在 \(1,2, \dots, n-1\) 中取值（共 \(n-1\) 种余数，即 \(n-1\) 个抽屉）。

将 \(n\) 个前缀和放入这 \(n-1\) 个抽屉中，由抽屉原理，必有两个前缀和 \(S_i\) 和 \(S_j \ (i \lt j)\) 模 \(n\) 同余，即 \(S_j \equiv S_i \pmod{n}\)，此时连续段之和 \(\sum \limits_{k=i+1}^j a_k = S_j - S_i\) 必能被 \(n\) 整除。

将边长为 \(1\) 的正方形连接各边中点，等分成 \(4\) 个边长为 \(\frac{1}{2}\) 的小正方形。将 \(5\) 个点放入 \(4\) 个小正方形中，由抽屉原理，至少有 \(2\) 个点落在同一个边长为 \(\frac{1}{2}\) 的小正方形内（或边界上）。边长为 \(\frac{1}{2}\) 的正方形内，任意两点间的最大距离即为其对角线长 \(d_{\max} = \sqrt{ \left( \frac{1}{2} \right) ^2 + \left( \frac{1}{2} \right) ^2 } = \frac{\sqrt{2}}{2}\)。因此，这两个点之间的距离必然不超过 \(\frac{\sqrt{2}}{2}\)。

将 \(6\) 个人抽象为无向图 \(G\) 的 \(6\) 个顶点 \(V = \{ v_1, v_2, \dots, v_6 \}\)，任意两个顶点之间都有连线（构成完全图 \(K_6\)）：若两人相互认识，则连线涂成红色；若两人相互不认识，则连线涂成蓝色。

问题严格转化为：证明在用 \(2\) 种颜色对 \(K_6\) 的 \(15\) 条边进行任意着色后，图中必然存在一个同色三角形（全红三角形或全蓝三角形）。

任意挑选一个顶点 \(A\)，在完全图 \(K_6\) 中，除去 \(A\) 之外还有 \(5\) 个顶点，因此从 \(A\) 出发共有 \(5\) 条边。这 \(5\) 条边只能涂上红色或蓝色（\(2\) 个颜色抽屉）。将 \(5\) 条边放入 \(2\) 种颜色抽屉中，根据推广抽屉原理，从 \(A\) 出发的 \(5\) 条边中，至少有 \(3\) 条边的颜色相同。

不妨设这 \(3\) 条同色边分别连接到顶点 \(B,C,D\)，且颜色均为红色。考察 \(B,C,D\) 这三个顶点之间的 \(3\) 条连线 \((B,C),(C,D),(D,B)\)：

• 情况 A：若这 \(3\) 条边中存在至少一条红边（例如边 \((B,C)\) 为红色），则顶点 \(A,B,C\) 构成的三角形三条边 \((A,B),(A,C),(B,C)\) 均为红色，即存在 \(3\) 个人两两相互认识。
• 情况 B：若这 \(3\) 条边中没有任何红边，这意味着 \((B,C),(C,D),(D,B)\) 全部为蓝边，则顶点 \(B,C,D\) 本身构成一个全蓝三角形，即存在 \(3\) 个人两两相互不认识。

综上所述，无论边如何着色，均能保证存在一个同色三角形，即群体中必存在 \(3\) 个人两两相互认识或两两相互不认识。

#include <iostream>
using namespace std;
const int N = (int)1e5 + 5;
int n, c[N], cnt[N];
// 判定第 $k$ 头奶牛是否能够拿到礼物
bool check(int k) {
    // 统计前 k-1 头奶牛的 c[i] 频次
    for (int i = 1; i < k; i++) {
        cnt[c[i]]++;
    }
    bool ok = true;
    int s = 0; // 记录 c[i]<x 的奶牛数量
    // 检查每一个可能的位置分割参数 x
    for (int x = 0; x < n; x++) {
        if (cnt[x] > 0) {
            // 根据抽屉原理，若 x>n-(k-s)，说明奶牛无法通过该瓶颈
            if (x > n - (k - s)) {
                ok = false;
                break;
            }
            s += cnt[x];
        }
    }
    // 清理 cnt 数组
    for (int i = 1; i < k; i++) {
        cnt[c[i]] = 0;
    }
    return ok;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    // 二分最大能够拿到礼物的奶牛编号
    int l = 1, r = n, ans = 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (check(m)) {
            ans = m; l = m + 1;
        } else {
            r = m - 1;
        }
    }
    // 输出无法拿到礼物的奶牛数量
    cout << n - ans << "\n";
    return 0;
}