主题

主题

 
   

E. GukiZ and GukiZiana

原题:http://codeforces.com/problemset/problem/551/E

Professor GukiZ was playing with arrays again and accidentally discovered new function, which he called GukiZiana. For given array a, indexed with integers from 1 to n, and number y, GukiZiana(a, y) represents maximum value of j - i, such that aj = ai = y. If there is no y as an element in a, then GukiZiana(a, y) is equal to  - 1. GukiZ also prepared a problem for you. This time, you have two types of queries:

First type has form 1 l r x and asks you to increase values of all ai such that l ≤ i ≤ r by the non-negative integer x.

Second type has form 2 y and asks you to find value of GukiZiana(a, y).

For each query of type 2, print the answer and make GukiZ happy!

Input

The first line contains two integers n, q (1 ≤ n ≤ 5 * 105, 1 ≤ q ≤ 5 * 104), size of array a, and the number of queries.

The second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 109), forming an array a.

Each of next q lines contain either four or two numbers, as described in statement:

If line starts with 1, then the query looks like 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109), first type query.

If line starts with 2, then th query looks like 2 y (1 ≤ y ≤ 109), second type query.

Output

For each query of type 2, print the value of GukiZiana(a, y), for y value for that query.

Examples

input

4 3

1 2 3 4

1 1 2 1

1 1 1 1

2 3

output

2

input

2 3

1 2

1 2 2 1

2 3

2 4

output

0

-1


题目大意:

给出一个长度为n的序列,给出m个操作:

  1. 给区间[l..r]的数字+w

  2. 查询权值为w的数字最右边出现的坐标与最左边出现的坐标的差。


个人解法;

我只能震惊!


看过去就是分块维护桶,再加上一个加法标记即可。

然后发现1e9不让开桶。又不能离散。

由于有了之前的经验,拿一个有序数组代替桶。

然后发现修改要重新排序,询问要二分查找。不能调块。

然而codeforces那些1s可以跑1e9的数据的评测机都给了10s!完全不虚……


代码如下:

http://codeforces.com/contest/551/submission/25944551

 
 
评论