Overview

Since the “next destination” from each cell is completely uniquely determined, this problem is essentially “starting from cell \(1\), find where you end up after traversing a functional graph \(K\) times.”
\(K\) can be as large as \(10^{18}\), which is extremely large, but since there are only \(N\) states, the movement must eventually fall into a repeating cycle.

Analysis

1. The next destination from each cell is uniquely determined

In this problem, if you know the current cell \(i\), the next cell is always uniquely determined.

• If \(i = N\), always stay at \(N\)
• If \(i = 1\):
  • \(A_1 + A_2\) is even \(\Rightarrow 2\)
  • Odd \(\Rightarrow 1\)
• If \(2 \le i \le N-1\):
  • \(A_i + A_{i+1}\) is even \(\Rightarrow i+1\)
  • Odd \(\Rightarrow i-1\)

In other words, this can be thought of as a graph where exactly one edge leaves each cell.
Such a graph is called a functional graph in competitive programming.

---

2. Naively simulating \(K\) steps is too slow

If you directly simulate \(K\) moves, the time complexity is \(O(K)\).
However, since \(K \le 10^{18}\), this is far too slow.

---

3. There are only \(N\) states, so a loop must eventually occur

The current state can be represented solely by the “current cell number.”
Since there are only \(N\) cells from \(1\) to \(N\), the moment the same cell is visited twice, all subsequent movement becomes a perfect repetition.

This means the sequence of moves always splits into:

• The initial part before entering the loop
• The periodic part that repeats forever after

For example, if the movement looks like:

\(1 \to 2 \to 3 \to 2 \to 3 \to 2 \to 3 \to \cdots\)

then:

• Before entering the loop: \(1\)
• Periodic part: \(2, 3\)

---

4. Record the first time each cell is visited

To exploit this, we record:

• visited[x] = the time when cell \(x\) was first visited
• order[t] = the cell you are at after \(t\) moves

while advancing step by step.

In the code, we set order[0] = 1, meaning
“after 0 moves, you are at cell 1.”

If the current cell pos has already been visited, that is the starting point of the loop.

• Let the loop start position be \(\mu\)
• Let the loop length be \(\lambda\)

Then:

• \(\mu = \text{visited[pos]}\)
• \(\lambda = \text{current time} - \mu\)

After that, the position after \(K\) moves is:

• If \(K\) is within the already recorded range: order[K]
• Otherwise, reduce it into the periodic part:
  order[mu + (K - mu) % lambda]

---

5. Why does this work?

Returning to the same cell means the transitions from that cell onward are exactly the same as before.
Therefore, subsequent movement repeats with period \(\lambda\).

Thus, even for large \(K\), it suffices to know “where in the loop you are,”
and there is no need to handle \(K\) directly.

Algorithm

1. If \(N=1\), the answer is always \(1\) regardless of how many moves are made.
2. For each cell \(i\), precompute the next cell nxt[i].
3. Starting from pos = 1, repeat the following:
   • If visited[pos] == -1:
     • visited[pos] = step
     • order.append(pos)
     • pos = nxt[pos]
     • step += 1
4. When you arrive at an already visited cell, a loop has been found.
   • mu = visited[pos]
   • cycle_len = step - mu
5. Compute the answer:
   • If K < len(order), the answer is order[K]
   • Otherwise, the answer is order[mu + (K - mu) % cycle_len]

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Using 1-indexed arrays makes it easy to directly correspond with the cell numbers in the problem statement.

• Note that order[0] represents the position “after 0 moves.” This allows the answer to be directly expressed in the form order[K].

• Parity checking is done with ((A[i] + A[i+1]) & 1) == 0.

• For cycle detection, “stop when the same cell is visited again” is sufficient. This is because the transition from each cell is uniquely determined.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    A = [0] + data[2:]

    if N == 1:
        print(1)
        return

    nxt = [0] * (N + 1)
    nxt[N] = N

    if ((A[1] + A[2]) & 1) == 0:
        nxt[1] = 2
    else:
        nxt[1] = 1

    for i in range(2, N):
        if ((A[i] + A[i + 1]) & 1) == 0:
            nxt[i] = i + 1
        else:
            nxt[i] = i - 1

    visited = [-1] * (N + 1)
    order = []

    pos = 1
    step = 0
    while visited[pos] == -1:
        visited[pos] = step
        order.append(pos)
        pos = nxt[pos]
        step += 1

    mu = visited[pos]
    cycle_len = step - mu

    if K < len(order):
        print(order[K])
    else:
        print(order[mu + (K - mu) % cycle_len])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.