[PA 2024] Liderzy

Luogu

IDLGP10351

Time3000ms

Memory1024MB

DifficultyP2

2024PA（波兰）

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 1 [Liderzy](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/lid/)** 根据 PWN 字典（一本波兰语字典），「*lider*」是指「政党、工会或其他社会组织的领导人」。另一方面，在算法中，序列中出现次数严格大于序列长度一半的元素被称为序列的领导元素。例如，序列 $[7, 2, 5, 7, 7]$ 的领导元素是数字 $7$，而序列 $[2, 3, 2, 3]$ 则没有领导元素。在本题中，我们将重点讨论「*lider*」一词的后一种含义。给定一个数列，你的任务是将它分成最小数目的数列（不一定连续），满足每个数列都有一个领导元素，并输出这个最小数目。可以证明这样的划分总是可能的。 ## Input 第一行一个整数 $n\ (1\le n\le 5\times 10^5)$，表示序列的长度。第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\le n)$，表示这个序列。 ## Output 输出一行一个整数表示答案。 [samples] ## Background PA 2024 1B ## Note 输入的序列可以划分为 $[1,3,1]$ 和 $[2,2]$，这样划分后的两个序列就都有领导元素了（分别为 $1$ 和 $2$）。

Samples

Input #1

5
1 2 3 1 2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[PA 2024] Liderzy",
    "description": {
      "content": "**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 1 [Liderzy](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/lid/)** 根据 PWN 字典（一本波兰语字典），「*lider*」是指「政党、工会或其他社会组织的领导人」。另一方面，在算法中，序列中出现次数",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10351"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 1 [Liderzy](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/lid/)**\n\n根据 PWN 字典（一本波兰语字典），「*lider*」是指「政党、工会或其他社会组织的领导人」。另一方面，在算法中，序列中出现次数...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments