Sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán đơn giản và dễ hiểu. Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy phần tử bằng cách liên tục lặp lại việc so sánh hai phần tử liền kề và hoán đổi vị trí của chúng nếu chung không theo thứ tự mong muốn. Quá trình này được lặp lại cho đến khi toàn bộ dãy đã được sắp xếp hoàn chỉnh.

Cho dãy số nguyên dương ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~.

Yêu cầu

Hãy viết chương trình đếm số lần hoán đổi vị trí các phần tử theo thuật toán sắp xếp nổi bọt để sắp xếp dãy tăng dần.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~ là số phần tử trong mảng.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9;\ 1 \le i \le n)~ cách nhau một khoảng trắng là các phần tử trong dãy.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lần hoán đổi các vị trí khi thực hiện thuật toán sắp xếp nổi bọt.

Ràng buộc dữ liệu

• 80% số điểm bài thi thỏa mãn ~1 \le n \le 10^3~.
• 100% số điểm bài thi thỏa mãn ~1 \le n \le 2 \times 10^5~.

Ví dụ

Ví dụ 1

INPUT

4
3 1 4 2

OUTPUT

3

Giải thích: Theo thuật toán sắp xếp nổi bọt có ~3~ lần hoán đổi vị trí các phần tử gồm:

• Lần thứ nhất, hoán đổi vị trí của hai phần tử ~(3, 1)~, dãy trở thành ~1, 3, 4, 2~.
• Lần thứ hai, hoán đổi vị trí của hai phần tử ~(2, 4)~, dãy trở thành ~1, 3, 2, 4~.
• Lần thứ ba, hoán đổi vị trí của hai phần tử ~(2, 3)~, dãy trở thành ~1, 2, 3, 4~.

Vùng đất thần tiên AlphaLand rộng lớn được chia thành nhiều khu vực khác nhau. Các khu vực được đánh số ~1, 2, 3, ...~.

Việc phân chia khu vực sinh sống, lao động, vui chơi cho người dân cũng khá kì lạ. Mỗi người dân được cấp một cái thẻ chứa một con số và họ chỉ được phép ra vào khu vực có số thứ tự là ước số của số thẻ. Các số trên thẻ của người dân được phép trùng nhau.

Mỗi dịp lễ hội thường niên, trưởng lão sẽ tập trung tât cả người dân về một khu vực để tổ chức tiệc mừng. Năm nay, ông quyết định mở tiệc tại khu vực mà tất cả người dân được phép ra vào khu vực đó có số thứ tự lớn nhất.

Nhận thấy rằng có một số thẻ đã cấp cho người dân làm ảnh hưởng đến việc chọn khu vực như trên, ông quyết định đổi cho một trong số họ cái thẻ mới để chọn được khu vực tổ chức tiệc có số thứ tự lớn hơn.

Yêu cầu

Cho danh sách ~n~ thẻ với các số tương ứng. Hãy viết chương trình tìm khu vực mà tất cả người dân được phép ra vào và khu vực đó có số thứ tự lớn nhất. Lưu ý, việc xác định khu vực thực hiện sau khi người dân được đổi thẻ.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9;\ 1 \le i \le n)~ cách nhau một khoảng trắng là số thẻ của người dân.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số thứ tự của khu vực tìm được theo yêu cầu trên.

Ràng buộc dữ liệu

• 40% số điểm bài thi thỏa mãn ~1 \le n \le 100;\ 1 \le a_i \le 100~.
• 80% số điểm bài thi thỏa mãn ~1 \le n \le 10^3~.
• 100% số điểm bài thi thỏa mãn ~1 \le n \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

3
4 2 8

OUTPUT

4

Giải thích:

• Thẻ số ~4~ đến được các khu vực ~\{1, 2, 4\}~;
• Thẻ số ~2~ đến được các khu vực ~\{1, 2\}~;
• Thẻ số ~8~ đến được các khu vực ~\{1, 2, 4, 8\}~.

Ban đầu khu vực dự kiến chọn là ~2~. Có thể đổi số thẻ ~2~ thành số ~4~. Với các thẻ ~4, 4, 8~ chọn khu vực có số thứ tự lớn hơn là ~4~.

Trong mùa hè năm nay, công ty game AlphaNet sẽ tổ chức giải đấu trực tuyến cho tất cả game thủ của mình. Danh sách tên các game thủ được đánh số thứ tự từ ~1~ đến ~n~. Mỗi game thủ có một ranking (thứ hạng trong game) khác nhau. Trước khi bắt đầu giải, ban tổ chức sẽ cho các game thủ giao lưu với nhau thông qua ~q~ lượt đấu đồng đội bằng cách ghép đôi ngẫu nhiên ở mỗi lượt đấu, ban tổ chức thực hiện ghép đôi ngẫu nhiên như sau:

Cho hệ thống sinh ngẫu hiện hai số ~u, v~ ~(u < v)~ để xác định nhóm các thành viên được chọn tham gia là các game thủ trong danh sách có số thứ tự từ ~u~ đến ~v~. Tiếp theo ban tổ chức sẽ chia nhóm các thành viên được chọn thành hai đội tương đối đều nhau về ranking. Ranking của một đội là tổng ranking của các thành viên trong đội. Do đó, ban tổ chức phải tính toán để xác định một vị trí sao cho đội lệch ranking giữa hai đội là nhỏ nhất và các thành viên trong đội phải có số thứ tự liên tiếp nhau trong danh sách (không quan trọng số lượng thành viên trong đội).

Yêu cầu

Cho một dãy ~n~ game thủ với ranking tương ứng và ~q~ cặp số nguyên ~u, v~ được hệ thống sinh ngẫu nhiên, hãy viết chương trình cho biết độ lệch ranking nhỏ nhất cuả từng lượt sau khi ban tổ chức thực hiện ghép đội ngẫu nhiên.

Dữ liệu đầu vào

Gồm ~q + 2~ dòng:

• Dòng thứ nhất chứa hai số nguyên dương ~n, q~ ~(1 \le n, q \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9;\ 1 \le i \le n)~ cách nhau một khoảng trắng.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ ~(1 \le u < v \le n)~ cách nhau một khoảng trắng tương ứng với mỗi lượt đấu.

Dữ liệu đầu ra

Gồm ~q~ dòng, dòng thứ ~i~ là kết quả tìm được ở lượt thứ ~i~.

Ràng buộc dữ liệu

• 40% số điểm của bài thi thỏa mãn ~1 \le n, q \le 100~.
• 80% số điểm của bài thi thỏa mãn ~1 \le n \le 10^3;\ 1 \le q \le 10^4~.
• 100% số điểm của bài thi thỏa mãn ~1 \le n, q \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

6 2
4 2 2 1 5 6
1 4
2 5

OUTPUT

1
0

Giải thích:

• Ở lượt thứ nhất, ranking của các game thủ số thứ tự từ ~1~ đến ~4~ là ~4, 3, 3, 1~. Ta có thể chia đội như sau:
  • ~\{4\}~ và ~\{2, 2, 1\}~, độ lệch ranking là ~1~.
  • ~\{4, 2\}~ và ~\{2, 1\}~, độ lệch ranking là ~3~.
  • ~\{4, 2, 2\}~ và ~\{1\}~, độ lệch ranking là ~7~.
• Ban tổ chức sẽ chia đội theo cách chia đầu tiên với độ lệch ranking nhỏ nhất là ~1~.
• Ở lượt thứ hai, ranking của các game thủ có số ~2~ đến ~5~ là ~2, 2, 1, 5~. Ban tổ chức sẽ chia đội thành ~\{2, 2, 1\}~ và ~\{5\}~ với độ lệch ranking nhỏ nhất là ~0~.