Diverse Segments solution codeforces

Diverse Segments solution codeforces

You are given an array aa of nn integers. Also you are given mm subsegments of that array. The left and the right endpoints of the jj-th segment are ljlj and rjrj respectively.

You are allowed to make no more than one operation. In that operation you choose any subsegment of the array aa and replace each value on this segment with any integer (you are also allowed to keep elements the same).

You have to apply this operation so that for the given mm segments, the elements on each segment are distinct. More formally, for each 1jm1≤j≤m all elements alj,alj+1,,arj1,arjalj,alj+1,…,arj−1,arj should be distinct.

You don’t want to use the operation on a big segment, so you have to find the smallest length of a segment, so that you can apply the operation to this segment and meet the above-mentioned conditions. If it is not needed to use this operation, the answer is 00.

Input

Diverse Segments solution codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1t1001≤t≤100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers nn and mm (1n,m21051≤n,m≤2⋅105) — the size of the array and the number of segments respectively.

The next line contains nn integers a1,a2,,ana1,a2,…,an (1ai1091≤ai≤109) — the elements of aa.

Each of the next mm lines contains two integers ljljrjrj (1ljrjn1≤lj≤rj≤n) — the left and the right endpoints of the jj-th segment.

It’s guaranteed that the sum of nn and the sum of mm over all test cases does not exceed 21052⋅105.

Output

For each test case output a single integer — the smallest length of a segment you can apply an operation on making the elements on all given segments distinct. If it is not needed to use the operation, output 00.

Example

Diverse Segments solution codeforces

input

Copy
5
7 3
1 1 2 1 3 3 5
1 4
4 5
2 4
5 2
10 1 6 14 1
4 5
2 4
4 5
5 7 5 6
2 2
1 3
2 4
3 3
3 4
7 3
2 2 2 7 8 2 2
4 4
4 4
5 5
1 1
123
1 1
output

Diverse Segments solution codeforces

Copy
2
0
1
0
0
Note

In the first test case you can perform the operation on the segment [1,2][1,2] and make a=[5,6,2,1,3,3,5]a=[5,6,2,1,3,3,5]. Then the elements on each segment are distinct.

  • On the segment [1,4][1,4] there are [5,6,2,1][5,6,2,1].
  • On the segment [4,5][4,5] there are [1,3][1,3].
  • On the segment [2,4][2,4] there are [6,2,1,3][6,2,1,3].

This way on each of the given segments all elements are distinct. Also, it is impossible to change any single integer to make elements distinct on each segment. That is why the answer is 22.

In the second test case the elements on each segment are already distinct, so we should not perform the operation.

In the third test case we can replace the first 55 by 11. This way we will get [1,7,5,6][1,7,5,6] where all elements are distinct so on each given segment all elements are distinct.

SOLUTION

Click here

Leave a Comment

Your email address will not be published.