Bubble Sort

Suppose the following C++ bubble sort code is executed.

bool changed = false;
for (int i = 1; i <= N + 1; i++) {
    changed = false;
    for (int j = 1; j <= N - i; j++) {
        if (A[j] > A[j + 1]) {
            changed = true;
            swap(A[j], A[j + 1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

Here, N is the size of the array, and A is the array to be sorted. The array uses indices from A[1] through A[N].

Determine the value printed when this code is executed.

The first line contains the array size N. N is a positive integer not greater than 500,000.

Each of the next N lines contains one value: A[1], A[2], ..., A[N]. Every value is an integer between 0 and 1,000,000, inclusive.

Print the value that the code outputs.