問題一覧 > 通常問題

No.3327 Shut Up, or I'll Throw a Polyomino at You

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 55
作問者 : のらら / テスター : ゆにたりー卿 👑 loop0919 DeltaStruct Apollo@Kuro Yama.can Rice_tawara459 あじゃじゃ eom2357 bolero elphe
お気に入りにしたユーザー ProblemId : 11735 / 自分の提出
問題文最終更新日: 2025-10-30 19:55:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第2回 岩井星人アンソロジープログラミングコンテスト Extra (順位表) の他の問題:

Problem Statement

$N$ people who have never done competitive programming (hereafter called Earthlings) are standing in a row from left to right. The $i$-th Earthling from the left has number $i$ and a (self-proclaimed) rating of $A_i$.

Iwai Seijin throws a polyomino at Earthlings $Q$ times.

Specifically, the information for the $i$-th throw is given as a pair of $2$ integers ($c, X$), as follows.

  • If $c=1$: throw a polyomino at the leftmost Earthling among those whose (self-proclaimed) rating is higher than $X$.
  • If $c=2$: throw a polyomino at the rightmost Earthling among those whose (self-proclaimed) rating is higher than $X$.

An Earthling hit by a polyomino leaves the row and never returns to it afterwards.

For each of the $Q$ polyominoes thrown by Iwai Seijin, output the number of the Earthling who leaves the row because of it. However, if no one leaves the row, output $-1$.

Constraints

  • $1 \leq N \leq 2×10^5$
  • $1 \leq Q \leq 2×10^5$
  • $1 \leq A_i, X \leq 10^9$
  • $c \in \{1, 2\}$
  • All inputs are integers.

Input

The input is given from standard input in the following format. Here, $query_i$ denotes the $i$-th query.

$N\ Q$
$A_1\ A_2\ ...\ A_N$
$query_1$
$query_2$
$:$
$query_Q$

Each query is given in the following format.

$c\ X$ 

Output

Output $Q$ lines.

On the $i$-th line, output the answer to the $i$-th query.

Sample

Sample 1
Input
5 4
3 5 8 1 4
1 4
2 7
2 4
1 3
Output
2
3
-1
5

The results of the queries are as follows.

  • In the $1$-st query, Earthling number $2$ leaves the row.
  • In the $2$-nd query, Earthling number $3$ leaves the row.
  • In the $3$-rd query, no Earthling with a (self-proclaimed) rating greater than $4$ remains in the row, so no one leaves the row.
  • In the $4$-th query, Earthling number $5$ leaves the row.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。