宾果 2

题目描述

有一个 $N \times N$ 的网格，从上数第 $i$ 行、从左数第 $j$ 列的格子中写着整数 $N \times (i-1) + j$。

在 $T$ 轮中依次宣布整数。第 $i$ 轮宣布整数 $A_i$，并将写着 $A_i$ 的格子做标记。

求首次达成宾果的轮次。如果在 $T$ 轮内没有达成宾果，输出 -1。

这里，达成宾果指满足以下至少一个条件：

• 存在一整行的 $N$ 个格子都被标记。
• 存在一整列的 $N$ 个格子都被标记。
• 存在一条对角线（从左上到右下，或从右上到左下）上的 $N$ 个格子都被标记。

输入格式

输入按以下格式从标准输入给出：

$N$ $T$
$A_1$ $A_2$ $\ldots$ $A_T$

输出格式

如果在 $T$ 轮内达成了宾果，输出首次达成宾果的轮次；否则输出 -1。

样例

3 5
5 1 8 9 7

4

3 5
4 2 9 7 5

-1

4 12
13 9 6 5 2 7 16 14 8 3 10 11

9

数据范围

• $2 \le N \le 2 \times 10^3$
• $1 \le T \le \min(N^2, 2 \times 10^5)$
• $1 \le A_i \le N^2$
• 若 $i \neq j$，则 $A_i \neq A_j$
• 所有输入值均为整数