1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>

struct big_number {
	std::string significand;
	std::string reversed_reminder;
	int zeroes = 0;
};

std::string to_string(const big_number& value) {
	std::string result = value.significand;
	result.append(value.zeroes, '0');
	result.append(value.reversed_reminder.rbegin(), value.reversed_reminder.rend());
	return result;
}

int digit_count(const big_number& value) {
	return value.significand.size() + value.reversed_reminder.size() + value.zeroes;
}

bool operator<(const big_number& lhs, const big_number& rhs) {
	int lhs_digits = digit_count(lhs);
	int rhs_digits = digit_count(rhs);
	if (lhs_digits < rhs_digits)
		return true;
	if (lhs_digits > rhs_digits)
		return false;
	if (lhs.significand < rhs.significand)
		return true;
	if (lhs.significand > rhs.significand)
		return false;
	if (lhs.reversed_reminder.size() < rhs.reversed_reminder.size())
		return true;
	if (lhs.reversed_reminder.size() > rhs.reversed_reminder.size())
		return false;
	return std::lexicographical_compare(
		lhs.reversed_reminder.rbegin(),
		lhs.reversed_reminder.rend(),
		rhs.reversed_reminder.rbegin(),
		rhs.reversed_reminder.rend()
	);
}

bool operator>(const big_number& lhs, const big_number& rhs) {
	return rhs < lhs;
}

bool operator<=(const big_number& lhs, const big_number& rhs) {
	return !(rhs < lhs);
}

bool operator>=(const big_number& lhs, const big_number& rhs) {
	return !(lhs < rhs);
}

void normalize(big_number& value) {
	while (!value.significand.empty() && value.significand.back() == '0') {
		value.significand.pop_back();
		value.zeroes++;
	}
	if (!value.reversed_reminder.empty() && digit_count(value) <= 16) {
		value.significand.append(value.zeroes, '0');
		value.significand.append(value.reversed_reminder.rbegin(), value.reversed_reminder.rend());
		value.zeroes = 0;
		value.reversed_reminder.clear();
		while (!value.significand.empty() && value.significand.back() == '0') {
			value.significand.pop_back();
			value.zeroes++;
		}
	}
}

bool is_prefix(const big_number& shorter, const big_number& longer) {
	if (shorter.significand.size() > longer.significand.size())
		return false;
	if (shorter.zeroes == 0)
		return std::equal(shorter.significand.begin(), shorter.significand.end(), longer.significand.begin());
	auto s = longer.significand;
	auto b = to_string(shorter);
	s.append(std::min(longer.zeroes, std::max(0, (int)(b.size() - s.size()))), '0');
	return s == b;
}

void append_zeroes_until_greater(big_number& shorter, const big_number& longer) {
	int shorter_digits = digit_count(shorter);
	int longer_digits = digit_count(longer);
	shorter.zeroes += longer_digits - shorter_digits;
	if (shorter <= longer)
		shorter.zeroes++;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::cin >> n;
	long long result = 0;
	big_number value;
	while (n--) {
		big_number loaded;
		std::cin >> loaded.significand;
		result -= loaded.significand.size();
		normalize(loaded);
		if (loaded > value) {
			value = std::move(loaded);
		} else if (is_prefix(loaded, value)) {
			auto pos = value.reversed_reminder.find_first_not_of('9');
			if (pos != std::string::npos) {
				value.reversed_reminder[pos]++;
				std::fill(value.reversed_reminder.begin(), value.reversed_reminder.begin() + pos, '0');
			} else if (value.zeroes > loaded.zeroes) {
				std::fill(value.reversed_reminder.begin(), value.reversed_reminder.end(), '0');
				value.reversed_reminder.push_back('1');
				value.zeroes--;
				normalize(value);
			} else {
				pos = value.significand.find_last_not_of('9');
				if (loaded.zeroes == 0 && pos != std::string::npos && pos >= loaded.significand.size()) {
					value.significand[pos]++;
					std::fill(value.significand.begin() + (pos + 1), value.significand.end(), '0');
					normalize(value);
				} else {
					append_zeroes_until_greater(loaded, value);
					value = std::move(loaded);
				}
			}
		} else {
			append_zeroes_until_greater(loaded, value);
			value = std::move(loaded);
		}
		result += digit_count(value);
	}
	std::cout << result;
	return 0;
}