#line 2 "/home/shogo314/cpp_include/sh-library/base/all" #include #line 5 "/home/shogo314/cpp_include/sh-library/base/container_func.hpp" #include #line 3 "/home/shogo314/cpp_include/sh-library/base/traits.hpp" #include #define HAS_METHOD(func_name) \ namespace detail { \ template \ struct has_##func_name##_impl : std::false_type {}; \ template \ struct has_##func_name##_impl().func_name())>> \ : std::true_type {}; \ } \ template \ struct has_##func_name : detail::has_##func_name##_impl::type {}; \ template \ inline constexpr bool has_##func_name##_v = has_##func_name::value; #define HAS_METHOD_ARG(func_name) \ namespace detail { \ template \ struct has_##func_name##_impl : std::false_type {}; \ template \ struct has_##func_name##_impl().func_name(std::declval()))>> \ : std::true_type {}; \ } \ template \ struct has_##func_name : detail::has_##func_name##_impl::type {}; \ template \ inline constexpr bool has_##func_name##_v = has_##func_name::value; HAS_METHOD(repr) HAS_METHOD(type_str) HAS_METHOD(initializer_str) HAS_METHOD(max) HAS_METHOD(min) HAS_METHOD(reversed) HAS_METHOD(sorted) HAS_METHOD(sum) HAS_METHOD(product) HAS_METHOD_ARG(count) HAS_METHOD_ARG(find) HAS_METHOD_ARG(lower_bound) HAS_METHOD_ARG(upper_bound) #define ENABLE_IF_T_IMPL(expr) std::enable_if_t = nullptr #define ENABLE_IF_T(...) ENABLE_IF_T_IMPL((__VA_ARGS__)) template using mem_value_type = typename C::value_type; template using mem_difference_type = typename C::difference_type; #line 9 "/home/shogo314/cpp_include/sh-library/base/container_func.hpp" #define METHOD_EXPAND(func_name) \ template )> \ inline constexpr auto func_name(const T &t) -> decltype(t.func_name()) { \ return t.func_name(); \ } #define METHOD_AND_FUNC_ARG_EXPAND(func_name) \ template )> \ inline constexpr auto func_name(const T &t, const U &u) \ -> decltype(t.func_name(u)) { \ return t.func_name(u); \ } \ template )> \ inline constexpr auto func_name(const T &t, const U &u) \ -> decltype(func_name(t.begin(), t.end(), u)) { \ using namespace std; \ return func_name(t.begin(), t.end(), u); \ } METHOD_EXPAND(reversed) template )> inline constexpr C reversed(C t) { std::reverse(t.begin(), t.end()); return t; } METHOD_EXPAND(sorted) template )> inline constexpr C sorted(C t) { std::sort(t.begin(), t.end()); return t; } template and std::is_invocable_r_v, mem_value_type>)> inline constexpr C sorted(C t, F f) { std::sort(t.begin(), t.end(), f); return t; } template inline constexpr void sort(C &t) { std::sort(t.begin(), t.end()); } template , mem_value_type>)> inline constexpr void sort(C &t, F f) { std::sort(t.begin(), t.end(), f); } template >)> inline constexpr void sort_by_key(C &t, F f) { std::sort(t.begin(), t.end(), [&](const mem_value_type &left, const mem_value_type &right) { return f(left) < f(right); }); } template inline constexpr void reverse(C &t) { std::reverse(t.begin(), t.end()); } METHOD_EXPAND(max) template )> inline constexpr mem_value_type max(const C &v) { assert(v.begin() != v.end()); return *std::max_element(v.begin(), v.end()); } template inline constexpr T max(const std::initializer_list &v) { return std::max(v); } METHOD_EXPAND(min) template )> inline constexpr mem_value_type min(const C &v) { assert(v.begin() != v.end()); return *std::min_element(v.begin(), v.end()); } template inline constexpr T min(const std::initializer_list &v) { return std::min(v); } METHOD_EXPAND(sum) template )> inline constexpr mem_value_type sum(const C &v) { return std::accumulate(v.begin(), v.end(), mem_value_type{}); } template inline constexpr T sum(const std::initializer_list &v) { return std::accumulate(v.begin(), v.end(), T{}); } METHOD_EXPAND(product) template )> inline constexpr mem_value_type product(const C &v) { return std::accumulate(v.begin(), v.end(), mem_value_type{1}, std::multiplies>()); } template inline constexpr T product(const std::initializer_list &v) { return std::accumulate(v.begin(), v.end(), T{1}, std::multiplies()); } METHOD_AND_FUNC_ARG_EXPAND(count) METHOD_AND_FUNC_ARG_EXPAND(find) METHOD_AND_FUNC_ARG_EXPAND(lower_bound) METHOD_AND_FUNC_ARG_EXPAND(upper_bound) template inline constexpr mem_value_type gcd(const C &v) { mem_value_type init(0); for (const auto &e : v) init = std::gcd(init, e); return init; } template inline constexpr mem_value_type average(const C &v) { assert(v.size()); return sum(v) / v.size(); } template inline constexpr mem_value_type median(const C &v) { assert(not v.empty()); std::vector u(v.size()); std::iota(u.begin(), u.end(), 0); std::sort(u.begin(), u.end(), [&](size_t a, size_t b) { return v[a] < v[b]; }); if (v.size() & 1) { return v[u[v.size() / 2]]; } // C++20 // return std::midpoint(v[u[v.size() / 2]], v[u[v.size() / 2 - 1]]); return (v[u[v.size() / 2]] + v[u[v.size() / 2 - 1]]) / 2; } template inline constexpr size_t index(const C &v, const U &x) { return std::distance(v.begin(), std::find(v.begin(), v.end(), x)); } template >)> inline constexpr mem_value_type mex(const C &v) { std::vector b(v.size() + 1); for (const auto &a : v) { if (0 <= a and a < b.size()) { b[a] = true; } } mem_value_type ret; for (size_t i = 0; i < b.size(); i++) { if (not b[i]) { ret = i; break; } } return ret; } template inline constexpr mem_difference_type bisect_left(const C &v, const mem_value_type &x) { return std::distance(v.begin(), lower_bound(v, x)); } template inline constexpr mem_difference_type bisect_right(const C &v, const mem_value_type &x) { return std::distance(v.begin(), upper_bound(v, x)); } #line 6 "/home/shogo314/cpp_include/sh-library/base/functions.hpp" template inline constexpr bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true; } return false; } template inline constexpr bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true; } return false; } template inline constexpr bool contains(const C &c, const T &t) { return c.find(t) != c.end(); } inline constexpr long long max(const long long &t1, const long long &t2) { return std::max(t1, t2); } inline constexpr long long min(const long long &t1, const long long &t2) { return std::min(t1, t2); } using std::abs; using std::gcd; using std::lcm; using std::size; template constexpr T extgcd(const T &a, const T &b, T &x, T &y) { T d = a; if (b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } template > and std::is_invocable_r_v>)> inline constexpr std::common_type_t binary_search(const M &ok, const N &ng, F f) { std::common_type_t _ok = ok, _ng = ng; assert(f(_ok)); while (std::abs(_ok - _ng) > 1) { std::common_type_t mid = (_ok + _ng) / 2; if (f(mid)) { _ok = mid; } else { _ng = mid; } } return _ok; } template > and std::is_invocable_r_v>)> inline constexpr std::common_type_t binary_search(const M &ok, const N &ng, F f) { std::common_type_t _ok = ok, _ng = ng; assert(f(_ok)); for (int i = 0; i < 100; i++) { std::common_type_t mid = (_ok + _ng) / 2; if (f(mid)) { _ok = mid; } else { _ng = mid; } } return _ok; } #line 8 "/home/shogo314/cpp_include/sh-library/base/io.hpp" namespace tuple_io { template std::basic_istream& read_tuple(std::basic_istream& is, Tuple& t) { is >> std::get(t); if constexpr (I + 1 < std::tuple_size_v) { return read_tuple(is, t); } return is; } template std::basic_ostream& write_tuple(std::basic_ostream& os, const Tuple& t) { os << std::get(t); if constexpr (I + 1 < std::tuple_size_v) { os << CharT(' '); return write_tuple(os, t); } return os; } }; // namespace tuple_io template std::basic_istream& operator>>(std::basic_istream& is, std::pair& p) { is >> p.first >> p.second; return is; } template std::basic_istream& operator>>(std::basic_istream& is, std::tuple& p) { return tuple_io::read_tuple, 0>(is, p); } template std::basic_istream& operator>>(std::basic_istream& is, std::array& a) { for (auto& e : a) is >> e; return is; } template std::basic_istream& operator>>(std::basic_istream& is, std::vector& v) { for (auto& e : v) is >> e; return is; } template std::basic_ostream& operator<<(std::basic_ostream& os, const std::pair& p) { os << p.first << CharT(' ') << p.second; return os; } template std::basic_ostream& operator<<(std::basic_ostream& os, const std::tuple& p) { return tuple_io::write_tuple, 0>(os, p); } template std::basic_ostream& operator<<(std::basic_ostream& os, const std::array& a) { for (size_t i = 0; i < N; ++i) { if (i) os << CharT(' '); os << a[i]; } return os; } template std::basic_ostream& operator<<(std::basic_ostream& os, const std::vector& v) { for (size_t i = 0; i < v.size(); ++i) { if (i) os << CharT(' '); os << v[i]; } return os; } template std::basic_ostream& operator<<(std::basic_ostream& os, const std::set& s) { for (auto itr = s.begin(); itr != s.end(); ++itr) { if (itr != s.begin()) os << CharT(' '); os << *itr; } return os; } /** * @brief 空行出力 */ void print() { std::cout << '\n'; } /** * @brief 出力して改行 * * @tparam T 型 * @param x 出力する値 */ template void print(const T& x) { std::cout << x << '\n'; } /** * @brief 空白区切りで出力して改行 * * @tparam T 1つ目の要素の型 * @tparam Tail 2つ目以降の要素の型 * @param x 1つ目の要素 * @param tail 2つ目以降の要素 */ template void print(const T& x, const Tail&... tail) { std::cout << x << ' '; print(tail...); } /** * @brief 空行出力 */ void err() { std::cerr << std::endl; } /** * @brief 出力して改行 * * @tparam T 型 * @param x 出力する値 */ template void err(const T& x) { std::cerr << x << std::endl; } /** * @brief 空白区切りで出力して改行 * * @tparam T 1つ目の要素の型 * @tparam Tail 2つ目以降の要素の型 * @param x 1つ目の要素 * @param tail 2つ目以降の要素 */ template void err(const T& x, const Tail&... tail) { std::cerr << x << ' '; err(tail...); } #line 3 "/home/shogo314/cpp_include/sh-library/base/type_alias.hpp" using ll = long long; using ull = unsigned long long; using ld = long double; template using vec = std::vector; template using ary = std::array; using str = std::string; using std::deque; using std::list; using std::map; using std::pair; using std::set; using pl = pair; using pd = pair; template using vv = vec>; template using vvv = vec>>; using vl = vec; using vvl = vv; using vvvl = vvv; using vs = vec; using vc = vec; using vi = vec; using vb = vec; template using vp = vec>; using vpl = vec; using vvpl = vv; using vd = vec; using vpd = vec; template using al = ary; template using aal = ary, N1>; template using val = vec>; template using ml = std::map; using mll = std::map; using sl = std::set; using spl = set; template using sal = set>; template using heap_max = std::priority_queue, std::less>; template using heap_min = std::priority_queue, std::greater>; #line 3 "/home/shogo314/cpp_include/sh-library/base/macro.hpp" #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define all(obj) (obj).begin(), (obj).end() #define reps(i, a, n) for (long long i = (a); i < (n); i++) #define rep(i, n) reps(i, 0, (n)) #define rrep(i, n) reps(i, 1, (n) + 1) #define repds(i, a, n) for (long long i = (n)-1; i >= (a); i--) #define repd(i, n) repds(i, 0, (n)) #define rrepd(i, n) repds(i, 1, (n) + 1) #define rep2(i, j, x, y) rep(i, x) rep(j, y) #define IN(a, x) a x; std::cin >> x; #define CHAR(x) char x; std::cin >> x; #define LL(x) ll x; std::cin >> x; #define VL(a,n) vl a(n); std::cin >> a; #define AL(a,k) al a; std::cin >> a; #define AAL(a,n,m) aal a; std::cin >> a; #define VC(a,n) vc a(n); std::cin >> a; #define VS(a,n) vs a(n); std::cin >> a; #define STR(s) str s; std::cin >> s; #define VPL(a,n) vpl a(n); std::cin >> a; #define VAL(a,n,k) val a(n); std::cin >> a; #define VVL(a,n,m) vvl a(n,vl(m)); std::cin >> a; #define SL(a,n) sl a;{VL(b,n);a=sl(all(b));} #line 8 "/home/shogo314/cpp_include/sh-library/base/vector_func.hpp" template std::vector sorted_idx(const std::vector &v) { std::vector ret(v.size()); std::iota(ret.begin(), ret.end(), 0); std::sort(ret.begin(), ret.end(), [&](std::ptrdiff_t i, std::ptrdiff_t j) { return v[i] < v[j]; }); return ret; } template inline std::vector &operator++(std::vector &v) { for (auto &e : v) e++; return v; } template inline std::vector operator++(std::vector &v, int) { auto res = v; for (auto &e : v) e++; return res; } template inline std::vector &operator--(std::vector &v) { for (auto &e : v) e--; return v; } template inline std::vector operator--(std::vector &v, int) { auto res = v; for (auto &e : v) e--; return res; } template )> inline std::vector &operator+=(std::vector &v1, const std::vector &v2) { if (v2.size() > v1.size()) { v1.resize(v2.size()); } for (size_t i = 0; i < v2.size(); i++) { v1[i] += v2[i]; } return v1; } template )> inline std::vector operator+(const std::vector &v1, const std::vector &v2) { std::vector res(v1); return res += v2; } template )> inline std::vector &operator+=(std::vector &v, const U &u) { for (T &e : v) { e += u; } return v; } template )> inline std::vector operator+(const std::vector &v, const U &u) { std::vector res(v); return res += u; } template )> inline std::vector operator+(const U &u, const std::vector &v) { std::vector res(v); return res += u; } template )> inline std::vector &operator*=(std::vector &v1, const std::vector &v2) { if (v2.size() > v1.size()) { v1.resize(v2.size()); } for (size_t i = 0; i < v2.size(); i++) { v1[i] *= v2[i]; } for (size_t i = v2.size(); i < v1.size(); i++) { v1[i] *= U(0); } return v1; } template )> inline std::vector operator*(const std::vector &v1, const std::vector &v2) { std::vector res(v1); return res *= v2; } template )> inline std::vector &operator*=(std::vector &v, const U &u) { for (T &e : v) { e *= u; } return v; } template )> inline std::vector operator*(const std::vector &v, const U &u) { std::vector res(v); return res *= u; } template )> inline std::vector operator*(const U &u, const std::vector &v) { std::vector res(v); return res *= u; } template inline std::vector &assign(std::vector &v1, const std::vector &v2) { v1.assign(v2.begin(), v2.end()); return v1; } template inline std::vector &extend(std::vector &v1, const std::vector &v2) { v1.insert(v1.end(), v2.begin(), v2.end()); return v1; } template )> inline std::vector &operator|=(std::vector &v1, const std::vector &v2) { return extend(v1, v2); } template )> inline std::vector &operator|=(std::vector &v, const U &u) { std::vector w(v); v.clear(); for (int i = 0; i < u; i++) { extend(v, w); } return v; } template )> inline std::vector operator|(const std::vector &v, const U &u) { std::vector res(v); return res |= u; } template )> inline std::vector operator|(const U &u, const std::vector &v) { std::vector res(v); return res |= u; } template inline std::vector abs(const std::vector &v) { std::vector ret; ret.reserve(v.size()); for (const T &e : v) ret.push_back(std::abs(e)); return ret; } template std::vector partial_sum(const std::vector &v) { std::vector ret(v.size()); std::partial_sum(v.begin(), v.end(), ret.begin()); return ret; } #line 2 "main.cpp" void solve() { LL(N); LL(M); VL(A, M); vl tmp(N); std::iota(all(tmp), 0); for (ll a : reversed(A)) { std::swap(tmp[a - 1], tmp[a]); ll x = index(tmp, 0); repd(i, x) { chmin(tmp[i], tmp[i + 1] + 1); } reps(i, x + 1, N) { chmin(tmp[i], tmp[i - 1] + 1); } } print(vl(tmp.begin() + 1, tmp.end())); } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve(); }