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
#include <stdio.h>

#define E 11
#define D (void)

long long int pot[E] = {1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10};

int log10(long long int x)
{
	int r = 0;

	while (x) {
		x /= 10;
		r++;
	}

	return r;
}

int main()
{
	int N, pe = 0, e;
	long long int x, res = 0, pr = 0, px = 0, tx, tpx, rx, rpx, pl = 0;

/* x * 10^e + pl * 10^k + pr */

	scanf("%d", &N);
	while (N--) {
		int a, b, cr, cl;
		scanf("%lld", &x);
		e = 0;
		if (pe >= E || pr + px * pot[pe] >= x) {

			a = log10(px);
			b = log10(x);
			e = pe - b + a;

			D("(a, b, e) = (%d, %d, %d)\n", a, b, e);

			if (a > b) {
				tpx = px / pot[a - b];
				rpx = px % pot[a - b];
				tx = x;
				rx = 0;
			} else if (a < b) {
				tpx = px;
				rpx = 0;
				tx = x / pot[b - a];
				rx = x % pot[b - a];
			} else {
				tpx = px;
				tx = x;
				rx = rpx = 0;
			}

			if (tpx > tx) {
				D("tpx > tx (%lld > %lld)\n", tpx, tx);
				e++;
				pr = 0;
				pl = 0;
			} else if (tpx == tx) {
				D("tpx == tx (%lld)\n", tpx);
				pr++;
				cr = log10(pr);
				cl = log10(pl);
				if (cr > e - cl) {
					D("cr, e, cl = %d, %d, %d\n", cr, e, cl);
					pl++;
					pr = 0;
					if (cr > e || log10(pl) > e) {
						pl = 0;
						e++;
					}
				} else if (a < b) {
					pl = 0;
				} else if (a > b) {
					pl = rpx;
				}
			} else {
				D("adding only zeros\n");
				pr = pl = 0;
			}

			if (e - b < E) {
				pr += pl * pot[e - b];
				pl = 0;
			}

			res += e;
			D("%lld (%lld, %lld, %lld)\n", pot[e] * x + pl * pot[e - b] + pr, x, pr, pl);
		} else {
			D("%lld [unchanged]\n", x);
		}


		px = x;
		pe = e;
	}

	printf("%lld\n", res);

	return 0;
}