#include <benchmark/benchmark.h>
#include <vector>
#include <random>
 
using namespace std;
 
static void memoryAccess (benchmark::State &state) {
    mt19937 rng(21);
    int n = state.range(0);
 
    vector<int> data(n);
    uniform_int_distribution<int> dist(0, n - 1);
    for (int &u : data) u = dist(rng);
 
    int index = dist(rng);
    for (auto _ : state) {
        data[index] = (data[index] == n - 1 ? 0 : data[index] + 1);
        benchmark::DoNotOptimize(data[index]);
        index = data[index];
    }
 
    state.SetBytesProcessed(state.iterations() * sizeof(int));
}
BENCHMARK(memoryAccess)->RangeMultiplier(2)->Range(1 << 2, 1 << 22);
 
BENCHMARK_MAIN();

I2luY2x1ZGUgPGJlbmNobWFyay9iZW5jaG1hcmsuaD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHJhbmRvbT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdGF0aWMgdm9pZCBtZW1vcnlBY2Nlc3MgKGJlbmNobWFyazo6U3RhdGUgJnN0YXRlKSB7CiAgICBtdDE5OTM3IHJuZygyMSk7CiAgICBpbnQgbiA9IHN0YXRlLnJhbmdlKDApOwoKICAgIHZlY3RvcjxpbnQ+IGRhdGEobik7CiAgICB1bmlmb3JtX2ludF9kaXN0cmlidXRpb248aW50PiBkaXN0KDAsIG4gLSAxKTsKICAgIGZvciAoaW50ICZ1IDogZGF0YSkgdSA9IGRpc3Qocm5nKTsKCiAgICBpbnQgaW5kZXggPSBkaXN0KHJuZyk7CiAgICBmb3IgKGF1dG8gXyA6IHN0YXRlKSB7CiAgICAgICAgZGF0YVtpbmRleF0gPSAoZGF0YVtpbmRleF0gPT0gbiAtIDEgPyAwIDogZGF0YVtpbmRleF0gKyAxKTsKICAgICAgICBiZW5jaG1hcms6OkRvTm90T3B0aW1pemUoZGF0YVtpbmRleF0pOwogICAgICAgIGluZGV4ID0gZGF0YVtpbmRleF07CiAgICB9CgogICAgc3RhdGUuU2V0Qnl0ZXNQcm9jZXNzZWQoc3RhdGUuaXRlcmF0aW9ucygpICogc2l6ZW9mKGludCkpOwp9CkJFTkNITUFSSyhtZW1vcnlBY2Nlc3MpLT5SYW5nZU11bHRpcGxpZXIoMiktPlJhbmdlKDEgPDwgMiwgMSA8PCAyMik7CgpCRU5DSE1BUktfTUFJTigpOw==