「マス \(i\) から \(1\) 回移動を行うとどのマスにいるか」は、今が何回目の移動であるかや、これまでにどのような移動を行ったかによりません。 これを \(f(i)\) と書くことにします。

\(f ^ 1(i)=f(i),f ^ {k+1}(i)=f(f ^ k(i))\) として \(f ^ k(i)\ (1\le k)\) を定めます。 求めるものは、\(f ^ K(1)\) です。

これは、ダブリングを利用して求めることができます。 具体的には、\(f ^ {2k}(i)=f ^ k(f ^ k(i))\) を利用することで、\(x\) 回の繰り返しで \(f ^ 1(i),f ^ 2(i),\ldots,f ^ {2 ^ x}(i)\) の値を求めることができます。 \(O(\log K)\) 回の繰り返しと \(O(\log K)\) 回の \(f ^ k\) の適用によって、\(f ^ K(1)\) を求めることができます。

時間計算量は \(O(N\log K)\) となります。

\(f(i)\) の性質を利用することで、この問題を \(O(N)\) 時間で解くこともできます（一度後ろに戻ったら、それ以降周期 \(2\) で移動を繰り返すことが示せます）。

実装例は以下のようになります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    long K;
    cin >> N >> K;
    vector<int> A(N);
    for (int& a : A) {
        cin >> a;
    }

    vector<int> f(N);
    for (int i = 0; i < N - 1; ++i) {
        if ((A[i] + A[i + 1]) % 2) {
            f[i] = max(0, i - 1);
        } else {
            f[i] = i + 1;
        }
    }
    f[N - 1] = N - 1;

    // f^k(i) から f^2k(i) を求める関数
    auto double_step = [N](vector<int> mapping) {
        vector<int> ret(N);
        for (int i = 0; i < N; ++i) {
            ret[i] = mapping[mapping[i]];
        }
        return ret;
    };

    // 「now から mapping にしたがって remain 回移動したときの位置」を不変量としてダブリングを行う
    int now = 0;
    vector<int> mapping = f;
    long remain = K;

    while (remain) {
        if (remain & 1) { // 奇数なら
            now = mapping[now]; // 一回移動して
            --remain; // 1 減らす
        }
        mapping = double_step(mapping); // 移動を倍にして
        remain /= 2; // 回数を半分にする
    }

    cout << now + 1 << endl; // 1-indexed にして出力
    return 0;
}

N, K = map(int, input().split())
A = list(map(int, input().split()))

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

# f^k(i) から f^2k(i) を求める関数
def double_step(mapping):
    ret = [0 for i in range(N)]
    for i in range(N):
        ret[i] = mapping[mapping[i]]
    return ret

# 「now から mapping にしたがって remain 回移動したときの位置」を不変量としてダブリングを行う
now = 0
mapping = f
remain = K

while remain > 0:
    if remain % 2 == 1: # 奇数なら
        now = mapping[now] # 一回移動して
        remain -= 1 # 1 減らす

    mapping = double_step(mapping) # 移動を倍にして
    remain //= 2 # 回数を半分にする

print(now + 1) # 1-indexed にして出力