← 返回题目列表

Codeforces · 551/E

E. GukiZ 和 GukiZiana

中文机器翻译题面 查看原题

GukiZ教授又在玩数组,无意中发现了一个新函数,他称之为GukiZiana。对于给定的数组 a(索引为 1 到 n 的整数)和数字 y,GukiZiana(a, y) 表示 j - i 的最大值,使得 aj = ai = y。如果a中没有y作为元素,那么GukiZiana(a, y)等于- 1。GukiZ还给你准备了一道题。这次,您有两种类型的查询:

1. 第一种类型的形式为 1 l r x 并要求您将所有 ai 的值增加非负整数 x,使得 l ≤ i ≤ r。
2. 第二种类型的形式为 2 y,要求您找到 GukiZiana(a, y) 的值。

对于类型 2 的每个查询,打印答案并让 GukiZ 高兴!

输入

第一行包含两个整数n、q (1 ≤ n ≤ 5 * 105, 1 ≤ q ≤ 5 * 104)、数组a的大小和查询次数。

第二行包含n个整数a1, a2, ... an (1 ≤ ai ≤ 109),构成数组a。

接下来的 q 行包含四个或两个数字,如语句中所述:

如果行以 1 开头,则查询类似于 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109),首先键入查询。

如果行以 2 开头,则第一个查询看起来像 2 y (1 ≤ y ≤ 109),第二类查询。

输出

对于类型 2 的每个查询,打印 GukiZiana(a, y) 的值,作为该查询的 y 值。

示例

输入 #1

4 3
1 2 3 4
1 1 2 1
1 1 1 1
2 3

输出 #1

2

输入 #2

2 3
1 2
1 2 2 1
2 3
2 4

输出 #2

0
-1