시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 8 7 6 100.000%

문제

Bubble sort is an algorithm to sort a sequence. Let’s say we are going to sort a sequence A0, A1, . . . , AN−1 of length N in non-decreasing order. Bubble sort swaps two adjacent numbers when they are not in the correct order. Swaps are done by repeatedly passing through the sequence. Precisely speaking, in a pass, we swap Ai and Ai+1 if Ai > Ai+1, for i = 0, 1, . . . , N − 2 in this order. It is known that any sequence can be sorted in non-decreasing order by some passes. For a sequence A, we define the number of passes by bubble sort as the number of passes needed to sort A using the above algorithm.

JOI-kun has a sequence A of length N. He is going to process Q queries of modifying values of A. To be specific, in the (j + 1)-th query (0 ≤ j ≤ Q − 1), the value of AXj is changed into Vj.

JOI-kun wants to know the number of passes by bubble sort for the sequence after processing each query.

입력

• line 1: N Q
• line 2: A0 A1 . . . AN−1
• line 3 + j (0 ≤ j ≤ Q − 1): Xj Vj

출력

• line 1 + j (0 ≤ j ≤ Q − 1): the number of passes by bubble sort for the sequence right after processing (j + 1)-th query.

서브태스크 1 (17점)

• 1 ≤ N ≤ 2 000
• 1 ≤ Q ≤ 2 000
• 1 ≤ Ai, Vj ≤ 1 000 000 000

서브태스크 2 (21점)

• 1 ≤ N ≤ 8 000
• 1 ≤ Q ≤ 8 000
• 1 ≤ Ai, Vj ≤ 1 000 000 000

서브태스크 3 (22점)

• 1 ≤ N ≤ 50 000
• 1 ≤ Q ≤ 50 000
• 1 ≤ Ai, Vj ≤ 100

서브태스크 4 (40점)

• 1 ≤ N ≤ 500 000
• 1 ≤ Q ≤ 500 000
• 1 ≤ Ai, Vj ≤ 1 000 000 000

4 2
1 2 3 4
0 3
2 1

1
2

예제 입력 2

11 12
11 4 13 6 7 3 5 12 4 10 11
8 11
4 4
6 20
0 2
7 2
3 18
5 9
0 6
8 8
9 4
0 8
6 18

5
5
5
4
6
6
6
7
7
7
7
7

힌트

Given a sequence A = {1, 2, 3, 4} of length N = 4 and Q = 2 queries: X = {0, 2}, V = {3, 1}.

1. For the first query, the value of A0 is changed into 3. We obtain A = {3, 2, 3, 4}.
2. For the second query, the value of A2 is changed into 1. We obtain A = {3, 2, 1, 4}.

Bubble sort for A = {3, 2, 3, 4}:

• A is not sorted, so the first pass starts. Since A0 > A1, we swap them to get A = {2, 3, 3, 4}. Since A1 ≤ A2, we don’t swap them. Since A2 ≤ A3, we don’t swap them.
• Now A is sorted, so the bubble sort ends.

Hence, the number of passes by bubble sort is 1 for A = {3, 2, 3, 4}.

Bubble sort for A = {3, 2, 1, 4}:

• A is not sorted, so the first pass starts. Since A0 > A1, we swap them to get A = {2, 3, 1, 4}. Since A1 > A2, we swap them to get A = {2, 1, 3, 4}. Since A2 ≤ A3, we don’t swap them.
• A is not sorted yet, so the second pass starts. Since A0 > A1, we swap them to get A = {1, 2, 3, 4}. Since A1 ≤ A2, we don’t swap them. Since A2 ≤ A3, we don’t swap them.
• Now A is sorted, so the bubble sort ends.

Hence, then number of passes by bubble sort is 2 for A = {3, 2, 1, 4}.

채점

• 예제는 채점하지 않는다.