2610. 合唱队形
1000ms
256MB
简单
动态规划
DFS
题目描述
小 A 在排合唱队形。现在有 $n$ 个学生,第 $i$ 个学生的身高为 $a_i$。
他认为,合唱队中有几个关键位置。具体而言,这些关键位置 $p$ 满足如下要求:
- $k+1 \leq p \leq n-k$;
- $p$ 之前的 $k$ 个人的身高满足非严格递减,即对于任意两个下标 $i$ 与 $i+1$,使得 $a_i \geq a_{i+1}$;
- $p$ 之后的 $k$ 个人的身高满足非严格递增,即对于任意两个下标 $i$ 与 $i+1$,使得 $a_i \leq a_{i+1}$;
小 A 想要知道有哪些位置是关键位置。
输入格式
第一行输入两个正整数 $n,k$;
第二行输入 $n$ 个正整数 $a_i$,表示每个学生的身高。
输出格式
输出一行,若干个正整数,以空格隔开,**升序**输出关键位置。如果没有关键位置,则输出 `No`。
样例 1
输入 (Input)
输出 (Output)
样例 2
输入 (Input)
输出 (Output)
对于 $30\%$ 的数据,$3 \leq n \leq 2000$,$1 \leq k \leq \dfrac{n}{2}$;
对于所有数据,满足 $3 \leq n \leq 5\times 10^5$,$1 \leq k \leq \dfrac{n}{2}$,$1 \leq a_i \leq 10^9$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功