1
#include <cstdio>
2
#include <iostream>
3
#include <algorithm>
4
#include <cmath>
5
#include <cstring>
6
using namespace std;
7

8
int t, n;
9
int main() {
10
  cin >> t;
11
  while(t--) {
12
    cin >> n;
13
    if(n == 1) printf("9\n");
14
    else if(n == 2) printf("98\n");
15
    else {
16
      printf("98");
17
      for(int i = 3, j = 9; i <= n; i++) {
18
        printf("%d", j);
19
        j++;
20
        if(j == 10) j = 0;
21
      }
22
      puts("");
23
    }
24
  }
25
  return 0;
26
}

1
#include <cstdio>
2
#include <iostream>
3
#include <algorithm>
4
#include <cmath>
5
#include <cstring>
6
using namespace std;
7

8
const int maxn = 3e5 + 17;
9
int t, n, a[maxn], ans, v[maxn], s[maxn];
10

11
inline int pos(int x) {
12
  if(a[x] > a[x - 1] && a[x] > a[x + 1]) return 1;
13
  else if(a[x] == a[x - 1] || a[x] == a[x + 1]) return 2;
14
  else if(a[x] < a[x - 1] && a[x] < a[x + 1]) return -1;
15
  return 0;
16
}
17

18
inline int val(int x) {
19
  if(x == 1 || x == n) return 0;
20
  return (abs(pos(x)) == 1) ? 1 : 0;
21
}
22

23
inline int ck(int x) {
24
  return val(x - 1) + val(x) + val(x + 1);
25
}
26

27
int main() {
28
  scanf("%d", &t);
29
  while(t--) {
30
    scanf("%d", &n);
31

32
    ans = 0;
33
    for(int i = 0; i <= n + 2; i++) a[i] = 0, v[i] = 0, s[i] = 0;
34

35
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
36
    if(n <= 4) {
37
      printf("0\n");
38
      continue;
39
    }
40

41
    for(int i = 1; i <= n; i++) v[i] = val(i);
42
    for(int i = 1; i <= n; i++) s[i] = v[i - 1] + v[i] + v[i + 1];
43

44
    // for(int i = 1; i <= n; i++) printf("%d%c", v[i], " \n"[i == n]);
45

46
    if(v[2] || v[n - 1]) ans = max(ans, 1);
47
    for(int i = 2; i < n; i++) {
48
      int st = a[i];
49
      for(a[i] = a[i - 1] - 1; a[i] <= a[i - 1] + 1; a[i]++) {
50
        int tmp = ck(i);
51
        // for(int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
52
          // if(a[i] == 6) printf("%d %d\n", tmp, s[i]);
53
        if(tmp < s[i]) ans = max(ans, s[i] - tmp);
54
      }
55
      for(a[i] = a[i + 1] - 1; a[i] <= a[i + 1] + 1; a[i]++) {
56
        int tmp = ck(i);
57
        if(tmp < s[i]) ans = max(ans, s[i] - tmp);
58
      }
59
      a[i] = st;
60
    }
61

62
    ans *= -1;
63
    for(int i = 1; i <= n; i++) ans += v[i];
64
    printf("%d\n", ans);
65
  }
66
  return 0;
67
}