무작위 섞기

Pang 교수는 세계 결승 대회에 진출할 팀을 고르고 있다. 지역 예선이 취소되어, 그는 무작위 섞기로 팀의 순위를 정한다. 전체 팀은 $n$개다. 그의 코드는 다음과 같다.

uint64_t x;//uint64_t represents 64-bit unsigned integer
int n;
uint64_t rand() {//this is a xor-shift random generator
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
}
int main() {
    cin >> n;
    cin >> x;
    for (int i = 1; i ≤ n; i++) {//random shuffle [1, 2,..., n]
        a[i] = i;
        swap(a[i], a[rand() % i + 1]);
    }
    for (int i = 1; i ≤ n; i++) {//print the result
        cout << a[i] << (i == n ? '\n' : ' ');
    }
}

교수는 코드를 컴파일하고 실행한 뒤, $n$과 특별한 음이 아닌 정수 $x$를 입력했다. 결과는 종이에 출력되었다.

하루가 지나, Pang 교수는 자신이 입력한 $x$를 잊어버렸다. 코드의 결과와 정수 $n$이 주어진다. Pang 교수가 입력했던 정수 $x$를 복원하라.

첫 줄에 팀의 수를 나타내는 정수 $n$($50\le n\le 100000$)이 주어진다.

다음 줄에는 Pang 교수의 코드가 출력한 결과인 정수 $n$개가 주어진다. 입력된 결과는 올바르다고 보장된다. 즉, 이 결과를 만들어 내는 정수 $x$($0\le x\le 2^{64}-1$)가 존재한다.

Pang 교수가 입력했던 정수 $x$($0\le x\le 2^{64}-1$)를 출력한다. 가능한 $x$가 여러 개라면 그중 아무거나 하나를 출력한다.

입력 예제의 둘째 줄은 페이지 너비에 맞추기 위해 줄바꿈되어 있다.