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
#include <iostream>
#include <string>
#include <vector>
#include <cstdint>
#include <cassert>
#include <iomanip>

const auto max_val = std::uint64_t(1) * 1000 * 1000 * 1000 * 1000 * 1000 * 100;

static unsigned int count_digits(std::uint64_t v)
{
	unsigned int c = 1;
	while(v >= 10) {
		++c;
		v /= 10;
	}
	return c;
}

class number {
	std::uint64_t val = 0;
	unsigned int digits = 0;
	
	char compare(const number &n) const {
		if (digits > n.digits) return 1;
		if (digits < n.digits) return -1;
		if (val > n.val) return 1;
		if (val < n.val) return -1;
		return 0;
	}
	void add(unsigned int v) {
		auto o = count_digits(val);
		val += v;
		if (val >= max_val) {
			val /= 10;
			++digits;
		}
		auto o2 = count_digits(val);
		digits += o2 - o;
	}
	void pot() {
		val *= 10;
		++digits;
		if (val >= max_val) {
			val /= 10;
		}
	}
public:
	bool operator == (const number &n) const { return compare(n) == 0; }
	bool operator < (const number &n) const { return compare(n) < 0; }
	bool operator <= (const number &n) const { return compare(n) <= 0; }
	bool operator > (const number &n) const { return compare(n) > 0; }

	number() = default;
	number(unsigned int v) : val(v), digits(count_digits(val)) { }
	
	size_t update_to(const number &n) {
		if (*this > n)
			return 0;
		if (*this == n) {
			pot();
			return 1;
		}
		const auto old_v = val;
		const auto old_ = digits;
		std::uint64_t max_diff = 1;
		for(auto i = old_; i < std::min(old_ + 20, n.digits); ++i) {
			auto old = val;			
			pot();
			if (old == val) break;
			max_diff *= 10;
		}
		digits = n.digits;
		const auto q = val;

		if (q < n.val) {
			if (n.val - q < max_diff - 1) {
				val = n.val;
				digits = n.digits;
				add(1);
			}
			else {
				pot();
			}
		}
		else if (q == n.val) {
			add(1);
		}
		return digits - old_;
	}
	friend std::ostream &operator << (std::ostream &o, const number &n) {
		o << n.val;
		for(auto i = 0u; i < n.digits - count_digits(n.val); ++i) o << '0';
		return o;
	}
};

int main()
{
	size_t count, added = 0;
	std::cin >> count;
	number current;
	
	for(auto i = 0; i < count; ++i) {
		unsigned int v;
		std::cin >> v;
		auto n = number(v);
		if (i == 363)
			i = i;
		auto d = n.update_to(current);
		added += d;
		assert(current < n);
		current = n;
		//std::cout << std::setw(12) << v << "  " << current << "  " << d << "\n";
		//if (i > 250) break;
		//if ((i % 1000) == 0) std::cout << i << "\r";
	}
	//std::cout << "\n";
	std::cout << added << "\n";
	return 0;
}