/**
* @title Template
*/
#include "gap.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
template <class T, class U>
bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T, class U>
bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
/**
* @title Chmin/Chmax
*/
class range {
public:
class iterator {
private:
int64_t M_position;
public:
iterator(int64_t position) noexcept: M_position(position) { }
void operator ++ () noexcept { ++M_position; }
bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
int64_t operator * () const noexcept { return M_position; }
};
class reverse_iterator {
private:
int64_t M_position;
public:
reverse_iterator(int64_t position) noexcept: M_position(position) { }
void operator ++ () noexcept { --M_position; }
bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
int64_t operator * () const noexcept { return M_position; }
};
private:
const iterator M_first, M_last;
public:
range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
iterator begin() const noexcept { return M_first; }
iterator end() const noexcept { return M_last; }
reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }
reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }
};
/**
* @title Range
*/
#include <type_traits>
#include <iterator>
template <class T>
class rev_impl {
public:
using iterator = decltype(std::declval<T>().rbegin());
private:
const iterator M_begin;
const iterator M_end;
public:
rev_impl(T &&cont) noexcept: M_begin(cont.rbegin()), M_end(cont.rend()) { }
iterator begin() const noexcept { return M_begin; }
iterator end() const noexcept { return M_end; }
};
template <class T>
rev_impl<T> rev(T &&cont) {
return rev_impl<T>(std::forward<T>(cont));
}
/**
* @title Reverser
*/
using i32 = int;
using i64 = long long int;
using u32 = unsigned int;
using u64 = unsigned long long int;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
#ifdef LOCAL
i32 Num, Task;
std::vector<i64> Values;
i64 Queries;
void MinMax(i64 s, i64 t, i64 *mn, i64 *mx) {
++Queries;
if (Task == 2) {
for (auto x: Values) {
if (s <= x && x <= t) {
++Queries;
}
}
}
assert(s <= t);
*mn = -1;
for (auto x: Values) {
if (x >= s) {
*mn = x;
break;
}
}
*mx = -1;
for (auto x: rev(Values)) {
if (x <= t) {
*mx = x;
break;
}
}
}
#endif
i64 findGap(i32 T, i32 N) {
if (T == 1) {
std::vector<i64> vec(N + 2);
i32 l = 0, r = N + 1;
vec[l] = -1;
vec[r] = 1000000000000000001;
while (r - l > 1) {
i64 mn, mx;
MinMax(vec[l] + 1, vec[r] - 1, &mn, &mx);
vec[l + 1] = mn;
vec[r - 1] = mx;
++l;
--r;
}
i64 res = 0;
for (auto i: range(1, N)) {
chmax(res, vec[i + 1] - vec[i]);
}
return res;
}
else {
i64 min, max;
MinMax(0, 1000000000000000000, &min, &max);
if (N == 2) {
return max - min;
}
std::vector<i64> nums;
nums.push_back(min);
i64 length = (max - min + (N - 1) - 1) / (N - 1);
for (auto i: range(0, N - 1)) {
i64 l = min + length * i + 1;
i64 r = std::min(max, l + length) - 1;
if (l > r) {
continue;
}
i64 mn, mx;
MinMax(l, r, &mn, &mx);
if (mn != -1) {
nums.push_back(mn);
}
if (mx != -1) {
nums.push_back(mx);
}
}
i64 res = length;
nums.push_back(max);
for (auto i: range(1, nums.size())) {
chmax(res, nums[i] - nums[i - 1]);
}
return res;
}
}
#ifdef LOCAL
int main() {
std::cin >> Task >> Num;
Values.resize(Num);
for (auto &x: Values) {
std::cin >> x;
}
std::cout << findGap(Task, Num) << '\n';
std::cout << Queries << '\n';
if (Task == 1) {
assert(Queries <= (Num + 1) / 2);
}
else {
assert(Queries <= 3 * Num);
}
return 0;
}
#endif
