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
#define ll long long
#include <iostream>
#include <string>


using namespace std;

class BigInt {
    ll length;
    string prefix, suffix;
  public:
    // suffix is written backwards :)
    BigInt(string p) { prefix = p; length = p.length(); suffix = "";}
    char atIndex(int at) {
    	// 0 <= at < length
	if (at < prefix.length()) {
		return prefix[at];
	} else if (at < (length - suffix.length())) {
		return '0';
	} else {
		return suffix[length-at-1];
	}

    }
    void incrementSuffix(int safeLength) {
    	for(int i = 0; i < suffix.length(); ++i) {
		if (length - i - 1 < safeLength) {
			// ALAAAARMM we try to edit chars which should be constant
			suffix = "";
			++length;
			return;
		}	
		if(suffix[i] < '9') {
		       	suffix[i] = suffix[i] + 1;
			return;
		} else {
			suffix[i] = '0';
		}
	}
	// if we are here suffix was '999...999' or ''
	suffix.append("1");
	// check if sum of lengths
	if (suffix.length() + prefix.length() > length) {
		// try to increment old prefix if it doesn't collide with safeLength
		int p = prefix.length()-1;
		for (int i = p; i > safeLength; --i) {
			if(prefix[i] < '9') {
				prefix[i] += 1;
				suffix[suffix.length() - 1 + i] = prefix[i];
				return;
			}
		}
		// it doesn't return so null suffix and make it longer
		++length;
		suffix = "";
	}
    }

    // update bigint with new prefix. make sure it will be greater, return number of digits added to new_prefix
    ll update(string new_prefix) {
	if(length < new_prefix.length()) {
		prefix = new_prefix;
		length = prefix.length();
		suffix = "";
		return 0;
	} else {
		// compare new_prefix with prefix
		// if it's greater: you can zero suffix, and keep the length. return number of filled zeroes (than prefix and sometimes suffix
		// if it's same: increment suffix (make sure you can), keep the length, return length - len(prefix)
		// if it's quicker: check if you can copy old, and increment suffix etc.
		// if it's lower than: you have to increment length and zero suffix
		for(int i = 0; i<length; ++i) {
			// length is at least such long as new_prefix.length
			char c = this->atIndex(i);
			if (i < new_prefix.length()) {
				if (c < new_prefix[i]) {
					prefix = new_prefix;
					suffix = "";	
					return length - new_prefix.length();
				} else if (c > new_prefix[i]) {
					++length;
					suffix = "";
					prefix = new_prefix;
					return length - new_prefix.length();
				}
			} else {
				// i is greater than new_prefix length and they were equal
				// we can copy rest of prefix (maybe increment by one if len(prefix) == length and it's possible in other case fill with zeroes and increment suffix
				// check if can increment suffix (if it doesn't collide with new_prefix)
				// if not you have to increment length :(
				this->incrementSuffix(new_prefix.length());
				return length - new_prefix.length();
			}
		}
		// they are equal!!!
		++length;
		suffix = "";
		return length - new_prefix.length();

	}
    }

    void print() {
    	for(int i=0; i<length; i++) {
		cout<<this->atIndex(i);
	}
	cout<<endl;
    }
};


int main() {
	ios_base::sync_with_stdio(0);
	ll res = 0;
	int n;
	cin>>n;
	string s;
	cin>>s;
	BigInt* b = new BigInt(s);
//	b->print();
	for(int i = 1; i<n; i++) {
		cin>>s;
		res += b->update(s);
//		b->print();
	}
	cout<<res<<endl;
	return 0;
}